## 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**

**Abstract:**

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 *lim*_{k → ∞ } α_{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**

**Abstract:**

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 *{f*_{i}}, a set *D* of clients, a lower-bound *M*, and connection costs *{c*_{ij}} 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 *.