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 = {10.4230/LIPIcs.FSTTCS.2008.1747},
annote = {Keywords: Network Design, Vertex Connectivity, BuyatBulk, RentorBuy, Approximation}
}
Keywords: 

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

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

2008 
Date of publication: 

05.12.2008 