Print Email Facebook Twitter An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem Title An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem Author Byrka, J. Aardal, K.I. Faculty Electrical Engineering, Mathematics and Computer Science Department Delft Institute of Applied Mathematics Date 2010-03-17 Abstract We obtain a 1.5-approximation algorithm for the metric uncapacitated facility location (UFL) problem, which improves on the previously best known 1.52-approximation algorithm by Mahdian, Ye, and Zhang. Note that the approximability lower bound by Guha and Khuller is 1.463 . . . . An algorithm is a (?f ,?c)-approximation algorithm if the solution it produces has total cost at most ?f ·F?+?c ·C?, where F? and C? are the facility and the connection cost of an optimal solution. Our new algorithm, which is a modification of the (1 + 2/e)-approximation algorithm of Chudak and Shmoys, is a (1.6774, 1.3738)-approximation algorithm for the UFL problem and is the first one that touches the approximability limit curve (?f ,1+2e??f ) established by Jain, Mahdian, and Saberi. As a consequence, we obtain the first optimal approximation algorithm for instances dominated by connection costs. When combined with a (1.11, 1.7764)-approximation algorithm proposed by Jain et al., and later analyzed by Mahdian et al., we obtain the overall approximation guarantee of 1.5 for the metric UFL problem. We also describe how to use our algorithm to improve the approximation ratio for the 3-level version of UFL. Subject facility locationapproximation algorithmsLP-rounding To reference this document use: http://resolver.tudelft.nl/uuid:6fced52a-3e9e-4684-bd31-0a3c27ad3b45 DOI https://doi.org/10.1137/070708901 Publisher Society for Industrial and Applied Mathematics ISSN 0097-5397 Source SIAM Journal of Computing, 39 (6), 2010 Part of collection Institutional Repository Document type journal article Rights (c) 2010 The Author(s)Society for Industrial and Applied Mathematics Files PDF Aardal.pdf 254.97 KB Close viewer /islandora/object/uuid:6fced52a-3e9e-4684-bd31-0a3c27ad3b45/datastream/OBJ/view