Greedy Strikes Back: Improved Facility Location Algorithms

Sudipto Guha*, Samir Khuller

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

294 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. We assume that the transportation costs form a metric. This problem is commonly referred to as the uncapacitated facility location problem. Application 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 algorithm by Shmoys, Tardos, and Aardal, can be used to obtain an approximation guarantee of 2.408. 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 prove a lower bound of 1.463 on the best possible approximation ratio, assuming NP ∉ DTIME[nO(log log n)].

Original languageEnglish (US)
Pages (from-to)228-248
Number of pages21
JournalJournal of Algorithms
Volume31
Issue number1
DOIs
StatePublished - Apr 1999

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Greedy Strikes Back: Improved Facility Location Algorithms'. Together they form a unique fingerprint.

Cite this