License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2008.1747
URN: urn:nbn:de:0030-drops-17475
Go to the corresponding LIPIcs Volume Portal

Chekuri, Chandra ; Korula, Nitish

Single-Sink Network Design with Vertex Connectivity Requirements

08004.ChekuriChandra.1747.pdf (0.4 MB)


We study single-sink network design problems in undirected graphs
with vertex connectivity requirements. The input to these problems
is an edge-weighted undirected graph $G=(V,E)$, a sink/root vertex
$r$, a set of terminals $T \subseteq V$, and integer $k$. The goal is
to connect each terminal $t \in T$ to $r$ via $k$ \emph{vertex-disjoint}
paths. In the {\em connectivity} problem, the objective is to find a
min-cost subgraph of $G$ that contains the desired paths. There is a
$2$-approximation for this problem when $k \le 2$ \cite{FleischerJW}
but for $k \ge 3$, the first non-trivial approximation was obtained
in the recent work of Chakraborty, Chuzhoy and Khanna
\cite{ChakCK08}; they describe and analyze an algorithm with an
approximation ratio of $O(k^{O(k^2)}\log^4 n)$ where $n=|V|$.

In this paper, inspired by the results and ideas in \cite{ChakCK08},
we show an $O(k^{O(k)}\log |T|)$-approximation bound for a simple
greedy algorithm. Our analysis is based on the dual of a natural
linear program and is of independent technical interest. We use the
insights from this analysis to obtain an $O(k^{O(k)}\log
|T|)$-approximation for the more general single-sink {\em
rent-or-buy} network design problem with vertex connectivity
requirements. We further extend the ideas to obtain a
poly-logarithmic approximation for the single-sink {\em buy-at-bulk}
problem when $k=2$ and the number of cable-types is a fixed
constant; we believe that this should extend to any fixed $k$. We
also show that for the non-uniform buy-at-bulk problem, for each
fixed $k$, a small variant of a simple algorithm suggested by
Charikar and Kargiazova \cite{CharikarK05} for the case of $k=1$
gives an $2^{O(\sqrt{\log |T|})}$ approximation for larger $k$.
These results show that for each of these problems, simple and
natural algorithms that have been developed for $k=1$ have good
performance for small $k > 1$.

BibTeX - Entry

  author =	{Chandra Chekuri and Nitish Korula},
  title =	{{Single-Sink Network Design with Vertex Connectivity Requirements}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{131--142},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Ramesh Hariharan and Madhavan Mukund and V Vinay},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-17475},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1747},
  annote =	{Keywords: Network Design, Vertex Connectivity, Buy-at-Bulk, Rent-or-Buy, Approximation}

Keywords: Network Design, Vertex Connectivity, Buy-at-Bulk, Rent-or-Buy, Approximation
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Issue Date: 2008
Date of publication: 05.12.2008

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