On the approximability of some network design problems

Julia Chuzhoy, Anupam Gupta, J. Naor, Amitabh Sinha

Research output: Contribution to journalArticlepeer-review


Consider the following classical network design problem: a set of terminals T = {ti} wishes 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 × 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 is governed by side constraints: edges can 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 this 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)), where V = n. In particular, we show that this inapproximability threshold holds for (i) the Priority-Steiner Tree problem, (ii) the (single-sink) Cost-Distance problem, and (iii) the single-sink version of an even more fundamental problem, Fixed Charge Network Flow. Our results provide a further breakthrough in the understanding of the level of complexity of network design problems. These are the first nonconstant hardness results known for all these problems.

Original languageEnglish (US)
Article number23
JournalACM Transactions on Algorithms
Issue number2
StatePublished - May 1 2008


  • Cost-distance
  • Fixed charge network flow
  • Hardness of approximation
  • Network design
  • Priority Steiner tree

ASJC Scopus subject areas

  • Mathematics (miscellaneous)


Dive into the research topics of 'On the approximability of some network design problems'. Together they form a unique fingerprint.

Cite this