An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem

J. Byrka

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

67 Citations (Scopus)
99 Downloads (Pure)

Abstract

We consider the metric uncapacitated facility location problem(UFL). In this paper we modify the (1¿+¿2/e)-approximation algorithm of Chudak and Shmoys to obtain a new (1.6774,1.3738)- approximation algorithm for the UFL problem. Our linear programing rounding algorithm is the first one that touches the approximability limit curve established by Jain et al. As a consequence, we obtain the first optimal approximation algorithm for instances dominated by connection costs. Our new algorithm - when combined with a (1.11,1.7764)-approxima- tion algorithm proposed by Jain, Mahdian and Saberi, and later analyzed by Mahdian, Ye and Zhang - gives a 1.5-approximation algorithm for the metric UFL problem. This algorithm improves over the previously best known 1.52-approximation algorithm by Mahdian, Ye and Zhang, and it cuts the gap with the approximability lower bound by 1/3. The algorithm is also used to improve the approximation ratio for the 3-level version of the problem.
Original languageEnglish
Title of host publicationProceedings of the 10th International Workshop on Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (APPROX 2007) and of the 11th International Workshop (RANDOM 2007) 20-22 August 2007, Princeton, New Jersey, USA
EditorsM. Charikar, K. Jansen, O. Reingold, J.D.P. Rolim
Place of PublicationBerlin
PublisherSpringer
Pages29-43
ISBN (Print)978-3-540-74207-4
DOIs
Publication statusPublished - 2007
Eventconference; APPROX 2007 and RANDOM 2007, Princeton, New Jersey, USA; 2007-08-20; 2007-08-22 -
Duration: 20 Aug 200722 Aug 2007

Publication series

NameLecture Notes in Computer Science
Volume4627
ISSN (Print)0302-9743

Conference

Conferenceconference; APPROX 2007 and RANDOM 2007, Princeton, New Jersey, USA; 2007-08-20; 2007-08-22
Period20/08/0722/08/07
OtherAPPROX 2007 and RANDOM 2007, Princeton, New Jersey, USA

Fingerprint

Dive into the research topics of 'An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem'. Together they form a unique fingerprint.

Cite this