On the Approximability of Network Design Problems

Consider the following classical network design problem: a set of terminals T = [ti wants to send traffic to a "root" r in an n-node graph G = (V,E). Each terminal ti sends di units of traffic, and enough bandwidth has to be allocated on the edges to permit this. However, bandwidth on an edge e can only be allocated in integral multiples of some base capacity ue --- and hence provisioning k x ue bandwidth on edge e incurs a cost of [k] times the cost of that edge. The objective is a minimum-cost feasible solution.This is one of many network design problems widely studied where the bandwidth allocation being governed by side constraints: edges may only allow a subset of cables to be purchased on them, or certain quality-of-service requirements may have to be met.In this work, we show that the above problem, and in fact, several basic problems in this general network design framework, cannot be approximated better than Ω(log log n) unless NP ⊆ DTIME (nO(log log log n). In particular, we show that this inapproximability threshold holds for (i) the Priority-Steiner Tree problem [7], (ii) the Cost-Distance problem [31], and the single-sink version of an even more fundamental problem, (iii) Fixed Charge Network Flow [33]. Our results provide a further breakthrough in the understanding of the level of complexity of network design problems. These are the first non-constant hardness results known for all these problems.