Nutov, Zeev ;
Kortsarz, Guy ;
Shalom, Eli
Approximating Activation EdgeCover and Facility Location Problems
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 EdgeCover 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 uvedge 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 subadditive 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_k1)/(1+k/theta), where H_k=sum_{i=1}^k 1/i. For the MinPower EdgeCover 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 EdgeCover and Facility Location Problems}},
booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
pages = {20:120:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771177},
ISSN = {18688969},
year = {2019},
volume = {138},
editor = {Peter Rossmanith and Pinar Heggernes and JoostPieter Katoen},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10964},
URN = {urn:nbn:de:0030drops109642},
doi = {10.4230/LIPIcs.MFCS.2019.20},
annote = {Keywords: generalized mincovering problem, activation edgecover, facility location, minimum power, approximation algorithm}
}
20.08.2019
Keywords: 

generalized mincovering problem, activation edgecover, facility location, minimum power, approximation algorithm 
Seminar: 

44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Issue date: 

2019 
Date of publication: 

20.08.2019 