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 :

{\bf Buy-at-bulk}
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)$.
Goal: Choose a subset of edges and a discount type for each chosen edge and route all demands to the sink (using chosen edges) such that the total cost is minimized.

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.

Paper available at http://www.cs.berkeley.edu/~kunal/acads/bb.ps