2026-07-23T15:19:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7858 2024-03-06T10:41:21Z ddc:004 open_access

Single-Sink Fractionally Subadditive Network Design Guruganesh, Guru Iglesias, Jennifer Ravi, R. Sanita, Laura Network design single-commodity flow approximation algorithms Steiner tree 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Guru Guruganesh and Jennifer Iglesias and R. Ravi and Laura Sanita 2017 Is Part Of LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2017.46 urn:nbn:de:0030-drops-78581 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.46 eng https://creativecommons.org/licenses/by/3.0/legalcode