Approximating k-generalized connectivity via collapsing HSTs

Danny Segev ()
Additional contact information
Danny Segev: Massachusetts Institute of Technology

Journal of Combinatorial Optimization, 2011, vol. 21, issue 3, No 6, 364-382

Abstract: Abstract An instance of the k -generalized connectivity problem consists of an undirected graph G=(V,E), whose edges are associated with non-negative costs, and a collection ${\mathcal{D}}=\{(S_{1},T_{1}),\ldots,(S_{d},T_{d})\}$ of distinct demands, each of which comprises a pair of disjoint vertex sets. We say that a subgraph ℋ⊆G connects a demand (S i ,T i ) when it contains a path with one endpoint in S i and the other in T i . Given an integer parameter k, the goal is to identify a minimum cost subgraph that connects at least k demands in ${\mathcal{D}}$ . Alon, Awerbuch, Azar, Buchbinder and Naor (SODA ’04) seem to have been the first to consider the generalized connectivity paradigm as a unified machinery for incorporating multiple-choice decisions into network formation settings. Their main contribution in this context was to devise a multiplicative-update online algorithm for computing log-competitive fractional solutions, and to propose provably-good rounding procedures for important special cases. Nevertheless, approximating the generalized connectivity problem in its unconfined form, where one makes no structural assumptions about the underlying graph and collection of demands, has remained an open question up until a recent O(log 2 nlog 2 d) approximation due to Chekuri, Even, Gupta and Segev (SODA ’08). Unfortunately, the latter result does not extend to connecting a pre-specified number of demands. Furthermore, even the simpler case of singleton demands has been established as a challenging computational task, when Hajiaghayi and Jain (SODA ’06) related its inapproximability to that of dense k -subgraph. In this paper, we present the first non-trivial approximation algorithm for k-generalized connectivity, which is derived by synthesizing several techniques originating in probabilistic embeddings of finite metrics, network design, and randomization. Specifically, our algorithm constructs, with constant probability, a feasible subgraph whose cost is within a factor of O(n 2/3⋅polylog(n,k)) of optimal. We believe that the fundamental approach illustrated in the current writing is of independent interest, and may be applicable in other settings as well.

Keywords: Approximation algorithms; Generalized connectivity; Probabilistic embedding into HSTs; Group Steiner tree; Dense k-subgraph (search for similar items in EconPapers)
Date: 2011
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-009-9256-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:21:y:2011:i:3:d:10.1007_s10878-009-9256-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-009-9256-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().