CENTER Carnegie Mellon School of Computer Science
Abstracts

Buy-at-bulk : LP rounding based algorithm
Kunal Talwar

Abstract:

The buy-at-bulk network design problem is to design a minimum cost network to satisfy some flow demands, by installing cables from an available set of cables with different costs per unit length and capacities, where the cable costs obey economies of scale. More formally, we consider the following problem :

Input: A graph $G=(V,E)$, a length function $l$ on edges, a distinguished node $t$ (the sink), a subset $D \subseteq V$ of vertices which to send one unit of flow each to the sink. There is concave cost function $c$ such that the cost per unit length of routing flow $f$ is $c(f)$.
Guha, Meyerson and Munagala(2001) gave the first constant factor approximation for this problem. Garg, Khandekar, Konjevod, Ravi, Salman and Sinha(2001) gave an $O(k)$ approximation (for a closely related problem) based on different LP rounding techniques. We use an LP rounding based algorithm along the lines of of Garg et.al. to get a constant factor approximation. This also shows that the integrality gap of a natural linear programming formulation is a constant.