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.

Received: 9 December 2005

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 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.