License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2019.20
URN: urn:nbn:de:0030-drops-109642
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10964/
Nutov, Zeev ;
Kortsarz, Guy ;
Shalom, Eli
Approximating Activation Edge-Cover 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 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},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10964},
URN = {urn:nbn:de:0030-drops-109642},
doi = {10.4230/LIPIcs.MFCS.2019.20},
annote = {Keywords: generalized min-covering problem, activation edge-cover, facility location, minimum power, approximation algorithm}
}
|
Keywords: |
|
generalized min-covering problem, activation edge-cover, facility location, minimum power, approximation algorithm |
|
Collection: |
|
44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
20.08.2019 |
