Improved LP-Rounding Approximation Algorithm for k-level Uncapacitated Facility Location
Improved LP-Rounding Approximation Algorithm for k-level Uncapacitated Facility Location
复制标题
DOI：
10.1007/978-3-642-31594-7_14
复制
发表时间：
2012-07
期刊：
影响因子：
--
通讯作者：
J. Byrka;Bartosz Rybicki
中科院分区：
文献类型：
--
作者：
J. Byrka;Bartosz Rybicki
We study the k-level uncapacitated facility location problem, where clients need to be connected with paths crossing open facilities ofktypes (levels). In this paper we give an approximation algorithm that for any constantk, in polynomial time, delivers solutions of cost at mostαktimesOPT, whereαkis an increasing function ofk, with limk→ ∞αk= 3.Our algorithm rounds a fractional solution to an extended LP formulation of the problem. The rounding builds upon the technique of iteratively rounding fractional solutions on trees (Garg, Konjevod, and Ravi SODA’98) originally used for the group Steiner tree problem.We improve the approximation ratio fork-UFL for allk≥ 3, in particular we obtain the ratio equal 2.02, 2.14, and 2.24 fork= 3,4, and 5.
