When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2019.20
URN: urn:nbn:de:0030-drops-109642
URL: https://drops.dagstuhl.de/opus/volltexte/2019/10964/
 Go to the corresponding LIPIcs Volume Portal

### Approximating Activation Edge-Cover and Facility Location Problems

 pdf-format:

### Abstract

What approximation ratio can we achieve for the Facility Location problem if whenever a client u connects to a facility v, the opening cost of v is at most theta times the service cost of u? We show that this and many other problems are a particular case of the Activation Edge-Cover problem. Here we are given a multigraph G=(V,E), a set R subseteq V of terminals, and thresholds {t^e_u,t^e_v} for each uv-edge e in E. The goal is to find an assignment a={a_v:v in V} to the nodes minimizing sum_{v in V} a_v, such that the edge set E_a={e=uv: a_u >= t^e_u, a_v >= t^e_v} activated by a covers R. We obtain ratio 1+max_{x>=1}(ln x)/(1+x/theta)~= ln theta - ln ln theta for the problem, where theta is a problem parameter. This result is based on a simple generic algorithm for the problem of minimizing a sum of a decreasing and a sub-additive set functions, which is of independent interest. As an application, we get the same ratio for the above variant of {Facility Location}. If for each facility all service costs are identical then we show a better ratio 1+max_{k in N}(H_k-1)/(1+k/theta), where H_k=sum_{i=1}^k 1/i. For the Min-Power Edge-Cover problem we improve the ratio 1.406 of [Calinescu et al, 2019] (achieved by iterative randomized rounding) to 1.2785. For unit thresholds we improve the ratio 73/60~=1.217 of [Calinescu et al, 2019] to 1555/1347~=1.155.

### BibTeX - Entry

```@InProceedings{nutov_et_al:LIPIcs:2019:10964,
author =	{Zeev Nutov and Guy Kortsarz and Eli Shalom},
title =	{{Approximating Activation Edge-Cover and Facility Location Problems}},
booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
pages =	{20:1--20:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-117-7},
ISSN =	{1868-8969},
year =	{2019},
volume =	{138},
editor =	{Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},