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.ESA.2017.46
URN: urn:nbn:de:0030-drops-78581
URL: https://drops.dagstuhl.de/opus/volltexte/2017/7858/
Go to the corresponding LIPIcs Volume Portal

Guruganesh, Guru ; Iglesias, Jennifer ; Ravi, R. ; Sanita, Laura

Single-Sink Fractionally Subadditive Network Design

pdf-format:
LIPIcs-ESA-2017-46.pdf (0.5 MB)

Abstract

We study a generalization of the Steiner tree problem, where we are given a weighted network G together with a collection of k subsets of its vertices and a root r. We wish to construct a minimum cost network such that the network supports one unit of flow to the root from every node in a subset simultaneously. The network constructed does not need to support flows from all the subsets simultaneously.

We settle an open question regarding the complexity of this problem for k=2, and give a 3/2-approximation algorithm that improves over a (trivial) known 2-approximation. Furthermore, we prove some structural results that prevent many well-known techniques from doing better than the known O(log n)-approximation. Despite these obstacles, we conjecture that this problem should have an O(1)-approximation. We also give an approximation result for a variant of the problem where the solution is required to be a path.

BibTeX - Entry

@InProceedings{guruganesh_et_al:LIPIcs:2017:7858,
  author =	{Guru Guruganesh and Jennifer Iglesias and R. Ravi and Laura Sanita},
  title =	{{Single-Sink Fractionally Subadditive Network Design}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{46:1--46:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Kirk Pruhs and Christian Sohler},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7858},
  URN =		{urn:nbn:de:0030-drops-78581},
  doi =		{10.4230/LIPIcs.ESA.2017.46},
  annote =	{Keywords: Network design, single-commodity flow, approximation algorithms, Steiner tree}
}

Keywords: Network design, single-commodity flow, approximation algorithms, Steiner tree
Collection: 25th Annual European Symposium on Algorithms (ESA 2017)
Issue Date: 2017
Date of publication: 01.09.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI