## Abstract

Consider the following classical network design problem: a set of terminals T = {t_{i}} wishes 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 × 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 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 (n^{O(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 language | English (US) |
---|---|

Article number | 23 |

Journal | ACM Transactions on Algorithms |

Volume | 4 |

Issue number | 2 |

DOIs | |

State | Published - May 1 2008 |

## Keywords

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

## ASJC Scopus subject areas

- Mathematics (miscellaneous)