Greedy strikes back: Improved facility location algorithms

Sudipto Guha*, Samir Khuller

*Corresponding author for this work

Research output: Contribution to conferencePaperpeer-review

134 Scopus citations

Abstract

A fundamental facility location problem is to choose the location of facilities, such as industrial plants and warehouses, to minimize the cost of satisfying the demand for some commodity. There are associated costs for locating the facilities, as well as transportation costs for distributing the commodities. This problem is commonly referred to as the uncapacitated facility location problem. Applications to bank account location and clustering, as well as many related pieces of work, are discussed by Cornuejols, Nemhauser and Wolsey. Recently, the first constant factor approximation algorithm for this problem was obtained by Shmoys, Tardos and Aardal. We show that a simple greedy heuristic combined with the Shmoys, Tardos and Aardal algorithm, can be used to derive a better approximation guarantee. We discuss a few variants of the problem, demonstrating better approximation factors for restricted versions of the problem. We also show that the problem is Max SNP-hard. However, the inapproximability constants derived from the Max SNP hardness are very close to one. By relating this problem to Set Cover, we can prove a better lower bound on the best possible approximation ratio.

Original languageEnglish (US)
Pages649-657
Number of pages9
StatePublished - 1998
EventProceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA
Duration: Jan 25 1998Jan 27 1998

Conference

ConferenceProceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms
CitySan Francisco, CA, USA
Period1/25/981/27/98

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Greedy strikes back: Improved facility location algorithms'. Together they form a unique fingerprint.

Cite this