On the approximability of some network design problems

Julia Chuzhoy, Anupam Gupta, Joseph Naor, Amitabh Sinha

Research output: Contribution to conferencePaperpeer-review


Consider the following classical network design problem: a set of terminals T = {t i} wants to send traffic to a "root" r in an n-node graph G = (V,E). Each terminal t i sends d i 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 u e - and hence provisioning k ^times; u e 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 (n o(log log log n)). In particular, we show that this inapproximability threshold holds for (i) the Priority-Steiner Tree problem, (ii) the Cost-Distance problem, and the single-sink version of an even more fundamental problem, (iii) 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 non-constant hardness results known for all these problems.

Original languageEnglish (US)
Number of pages9
StatePublished - 2005
EventSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States
Duration: Jan 23 2005Jan 25 2005


OtherSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityVancouver, BC

ASJC Scopus subject areas

  • Software
  • General Mathematics


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

Cite this