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