SCIENCE@home

An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem

J. Byrka,K. Aardal

Published 2006 in SIAM journal on computing (Print)

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 $(\gamma_f, 1+2e^{-\gamma_f})$ 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.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-25 of 25 references · Page 1 of 1

CITED BY

Showing 1-100 of 252 citing papers · Page 1 of 3

123
Next