1 Search Results for "Shalom, Eli"

Document
DOI: 10.4230/LIPIcs.MFCS.2019.20
Approximating Activation Edge-Cover and Facility Location Problems

Authors: Zeev Nutov, Guy Kortsarz, and Eli Shalom

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

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.
Cite as

Zeev Nutov, Guy Kortsarz, and Eli Shalom. Approximating Activation Edge-Cover and Facility Location Problems. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{nutov_et_al:LIPIcs.MFCS.2019.20,
  author =	{Nutov, Zeev and Kortsarz, Guy and Shalom, Eli},
  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 =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.20},
  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}
}
  • Refine by Author
  • 1 Kortsarz, Guy
  • 1 Nutov, Zeev
  • 1 Shalom, Eli

  • Refine by Classification
  • 1 Mathematics of computing → Approximation algorithms

  • Refine by Keyword
  • 1 activation edge-cover
  • 1 approximation algorithm
  • 1 facility location
  • 1 generalized min-covering problem
  • 1 minimum power

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact