Invited Session Fri.2.H 3013

Friday, 13:15 - 14:45 h, Room: H 3013

Cluster 2: Combinatorial optimization [...]

Facility location


Chair: Jarosław Byrka



Friday, 13:15 - 13:40 h, Room: H 3013, Talk 1

Bartosz Rybicki
Improved LP-rounding approximation algorithm for k-level uncapacitated facility location

Coauthor: Jarosław Byrka


We study the k-level uncapacitated facility location problem, where clients need to be connected with paths crossing open facilities of k types (levels). In this paper we give 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 limk → ∞ αk = 3.
We improve the approximation ratio for k-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.



Friday, 13:45 - 14:10 h, Room: H 3013, Talk 2

Sara Ahmadian
Improved approximation guarantees for lower-bounded facility location

Coauthor: Chaitanya Swamy


We consider the lower-bounded facility location (LBFL) problem, which is a generalization of uncapacitated facility location (UFL), where each open facility is required to serve a minimum amount of demand. More formally, an instance I of LBFL is specified by a set F of facilities with facility-opening costs {fi}, a set D of clients, a lower-bound M, and connection costs {cij} specifying the cost of assigning a client j to a facility i. The goal is to open a subset of facilities and assign each client to an open facility, so that each open facility serves at least M clients, in a cost-efficeint manner.
We improve the current best approximation ratio for LBFL (550 by Svitkina) to 83. Our improvement comes from a variety of ideas in algorithm design and analysis. Our chief algorithmic novelty is to reduce a more-structured LBFL instance to a problem we introduce, called capacity-discounted UFL (CDUFL). CDUFL is a special case of capacitated facility location (CFL) where facilities are either uncapacitated, or have finite capacity and zero opening costs. We give a simple local-search algorithm for CDUFL that achieves the approximation ratio of 1+√2 .


  The system of instant Virginia Loans Online allows any adult U.S. citizen. In this section we give only a brief summary recommendation for admission of Levitra. Full information can be found in the instructions for receiving medications with vardenafil.