Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-15T17:08:40.221Z Has data issue: false hasContentIssue false

An ex-post bound on the greedy heuristic for the uncapacitated facility location problem

Published online by Cambridge University Press:  12 October 2006

Jean-Michel Thizy*
Affiliation:
GEMO, ESDES, Lyon & School of Management, University of Ottawa, Ottawa, Ontario, Canada; . This article was submitted while the author was on a sabbatical leave at the Industrial Engineering & Computer Sciences Division of the École Nationale Supérieure des Mines de Saint-Etienne.
Get access

Abstract

A bound for the greedy heuristic applied to the K-facility location problem can be calculated,using values gathered during the calculation of the heuristic. The bound strengthens awell-known bound for the heuristic. Computational experiments show that this bound can bebeneficial when the number of facilities is small or close to the total number of potential sites. In addition, it is consistent with previous results about the influence of the data characteristicsupon the optimal value.

Information

Type
Research Article
Copyright
© EDP Sciences, 2006

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable