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 majority of financial loan companies provide the service of getting Payday Loans North Carolina for U.S. citizens. What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.