Single-sink fractionally subadditive network design

Guru Guruganesh; Jennifer Iglesias; R. Ravi; Laura Sanità

doi:10.4230/LIPIcs.ESA.2017.46

Single-sink fractionally subadditive network design

Guru Guruganesh, Jennifer Iglesias, R. Ravi, Laura Sanità

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

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.

Original language	English
Title of host publication	25th European Symposium on Algorithms, ESA 2017
Editors	Christian Sohler, Christian Sohler, Kirk Pruhs
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Electronic)	9783959770491
DOIs	https://doi.org/10.4230/LIPIcs.ESA.2017.46
Publication status	Published - 1 Sept 2017
Externally published	Yes
Event	25th European Symposium on Algorithms, ESA 2017 - Vienna, Austria Duration: 4 Sept 2017 → 6 Sept 2017

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	87
ISSN (Print)	1868-8969

Conference

Conference	25th European Symposium on Algorithms, ESA 2017
Country/Territory	Austria
City	Vienna
Period	4/09/17 → 6/09/17

Funding

∗ Full version available at: https://arxiv.org/abs/1707.01487. † This material is based upon work supported in part by National Science Foundation awards CCF-1319811,CCF-1536002, and CCF-1617790. ‡ This material is based upon work supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. 2013170941.

Keywords

Approximation algorithms
Network design
Single-commodity flow
Steiner tree

Access to Document

10.4230/LIPIcs.ESA.2017.46

Cite this

Guruganesh, G., Iglesias, J., Ravi, R., & Sanità, L. (2017). Single-sink fractionally subadditive network design. In C. Sohler, C. Sohler, & K. Pruhs (Eds.), 25th European Symposium on Algorithms, ESA 2017 Article 46 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 87). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2017.46

@inproceedings{36bc7061162f439abd39a6a8777f143e,

title = "Single-sink fractionally subadditive network design",

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.",

keywords = "Approximation algorithms, Network design, Single-commodity flow, Steiner tree",

author = "Guru Guruganesh and Jennifer Iglesias and R. Ravi and Laura Sanit{\`a}",

year = "2017",

month = sep,

day = "1",

doi = "10.4230/LIPIcs.ESA.2017.46",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

editor = "Christian Sohler and Christian Sohler and Kirk Pruhs",

booktitle = "25th European Symposium on Algorithms, ESA 2017",

note = "25th European Symposium on Algorithms, ESA 2017 ; Conference date: 04-09-2017 Through 06-09-2017",

}

Guruganesh, G, Iglesias, J, Ravi, R & Sanità, L 2017, Single-sink fractionally subadditive network design. in C Sohler, C Sohler & K Pruhs (eds), 25th European Symposium on Algorithms, ESA 2017., 46, Leibniz International Proceedings in Informatics, LIPIcs, vol. 87, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 25th European Symposium on Algorithms, ESA 2017, Vienna, Austria, 4/09/17. https://doi.org/10.4230/LIPIcs.ESA.2017.46

Single-sink fractionally subadditive network design. / Guruganesh, Guru; Iglesias, Jennifer; Ravi, R. et al.
25th European Symposium on Algorithms, ESA 2017. ed. / Christian Sohler; Christian Sohler; Kirk Pruhs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. 46 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 87).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Single-sink fractionally subadditive network design

AU - Guruganesh, Guru

AU - Iglesias, Jennifer

AU - Ravi, R.

AU - Sanità, Laura

PY - 2017/9/1

Y1 - 2017/9/1

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Network design

KW - Single-commodity flow

KW - Steiner tree

UR - http://www.scopus.com/inward/record.url?scp=85030528073&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ESA.2017.46

DO - 10.4230/LIPIcs.ESA.2017.46

M3 - Conference contribution

AN - SCOPUS:85030528073

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 25th European Symposium on Algorithms, ESA 2017

A2 - Sohler, Christian

A2 - Pruhs, Kirk

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 25th European Symposium on Algorithms, ESA 2017

Y2 - 4 September 2017 through 6 September 2017

ER -

Single-sink fractionally subadditive network design

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this