License
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://drops.dagstuhl.de/opus/volltexte/2019/10964/
Go to the corresponding LIPIcs Volume Portal


Nutov, Zeev ; Kortsarz, Guy ; Shalom, Eli

Approximating Activation Edge-Cover and Facility Location Problems

pdf-format:
LIPIcs-MFCS-2019-20.pdf (0.6 MB)


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
Seminar: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Issue Date: 2019
Date of publication: 23.08.2019


DROPS-Home | Imprint | Privacy Published by LZI