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

J. Byrka

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

71 Citaten (Scopus)
166 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
TitelProceedings 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
RedacteurenM. Charikar, K. Jansen, O. Reingold, J.D.P. Rolim
Plaats van productieBerlin
UitgeverijSpringer
Pagina's29-43
ISBN van geprinte versie978-3-540-74207-4
DOI's
StatusGepubliceerd - 2007
Evenementconference; APPROX 2007 and RANDOM 2007, Princeton, New Jersey, USA; 2007-08-20; 2007-08-22 -
Duur: 20 aug. 200722 aug. 2007

Publicatie series

NaamLecture Notes in Computer Science
Volume4627
ISSN van geprinte versie0302-9743

Congres

Congresconference; APPROX 2007 and RANDOM 2007, Princeton, New Jersey, USA; 2007-08-20; 2007-08-22
Periode20/08/0722/08/07
AnderAPPROX 2007 and RANDOM 2007, Princeton, New Jersey, USA

Vingerafdruk

Duik in de onderzoeksthema's van 'An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem'. Samen vormen ze een unieke vingerafdruk.

Citeer dit