Volume 40, Number 2, April-June 2006ROADEF 03
|Page(s)||143 - 167|
|Published online||12 October 2006|
An ex-post bound on the greedy heuristic for the uncapacitated facility location problem
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.
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 a well-known bound for the heuristic. Computational experiments show that this bound can be beneficial 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 characteristics upon the optimal value.
© EDP Sciences, 2006
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.