Chekuri, Chandra ;
Korula, Nitish
SingleSink Network Design with Vertex Connectivity Requirements
Abstract
We study singlesink network design problems in undirected graphs
with vertex connectivity requirements. The input to these problems
is an edgeweighted 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{vertexdisjoint}
paths. In the {\em connectivity} problem, the objective is to find a
mincost 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 nontrivial 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 singlesink {\em
rentorbuy} network design problem with vertex connectivity
requirements. We further extend the ideas to obtain a
polylogarithmic approximation for the singlesink {\em buyatbulk}
problem when $k=2$ and the number of cabletypes is a fixed
constant; we believe that this should extend to any fixed $k$. We
also show that for the nonuniform buyatbulk 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
@InProceedings{chekuri_et_al:LIPIcs:2008:1747,
author = {Chandra Chekuri and Nitish Korula},
title = {{SingleSink Network Design with Vertex Connectivity Requirements}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
pages = {131142},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897088},
ISSN = {18688969},
year = {2008},
volume = {2},
editor = {Ramesh Hariharan and Madhavan Mukund and V Vinay},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1747},
URN = {urn:nbn:de:0030drops17475},
doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2008.1747},
annote = {Keywords: Network Design, Vertex Connectivity, BuyatBulk, RentorBuy, Approximation}
}
Keywords: 

Network Design, Vertex Connectivity, BuyatBulk, RentorBuy, Approximation 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science

Issue date: 

2008 
Date of publication: 

05.12.2008 