Print Email Facebook Twitter Improved Approximation Algorithm for k-level Uncapacitated Facility Location Problem (with Penalties) Title Improved Approximation Algorithm for k-level Uncapacitated Facility Location Problem (with Penalties) Author Byrka, Jaroslaw (University of Wroclaw) Li, S. (TU Delft Discrete Mathematics and Optimization) Rybicki, Bartosz (University of Wroclaw) Date 2014-11-04 Abstract We study the k-level uncapacitated facility location problem (k-level UFL) in which clients need to be connected with paths crossing open facilities of k types (levels). In this paper we first propose an approximation algorithm that for any constant k, in polynomial time, delivers solutions of cost at most α_{k} times OPT, where α_{k} is an increasing function of k, with lim_{k→∞}α_{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 for k-level UFL for all k ≥ 3, in particular we obtain the ratio equal 2.02, 2.14, and 2.24 for k = 3,4, and 5. Second, we give a simple interpretation of the randomization process (Li ICALP’2011) for 1-level UFL in terms of solving an auxiliary (factor revealing) LP. Armed with this simple view point, we exercise the randomization on our algorithm for the k-level UFL. We further improve the approximation ratio for all k ≥ 3, obtaining 1.97, 2.09, and 2.19 for k = 3,4, and 5. Third, we extend our algorithm to the k-level UFL with penalties (k-level UFLWP), in which the setting is the same as k-level UFL except that the planner has the option to pay a penalty instead of connecting chosen clients. Subject Approximation algorithmsFacility location To reference this document use: http://resolver.tudelft.nl/uuid:0eebc93e-92e5-4e65-8307-a5d5e23b5238 DOI https://doi.org/10.1007/s00224-014-9575-3 ISSN 1432-4350 Source Theory of Computing Systems, 58 (1), 19-44 Part of collection Institutional Repository Document type journal article Rights © 2014 Jaroslaw Byrka, S. Li, Bartosz Rybicki Files PDF 18846644.pdf 1.14 MB Close viewer /islandora/object/uuid:0eebc93e-92e5-4e65-8307-a5d5e23b5238/datastream/OBJ/view