Approximability of capacitated network design

Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, Nitish Korula

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In the capacitated survivable network design problem (Cap-SNDP), we are given an undirected multi-graph where each edge has a capacity and a cost. The goal is to find a minimum cost subset of edges that satisfies a given set of pairwise minimum-cut requirements. Unlike its classical special case of SNDP when all capacities are unit, the approximability of Cap-SNDP is not well understood; even in very restricted settings no known algorithm achieves a o(m) approximation, where m is the number of edges in the graph. In this paper, we obtain several new results and insights into the approximability of Cap-SNDP. We give an O(logn) approximation for a special case of Cap-SNDP where the global minimum cut is required to be at least R, by rounding the natural cut-based LP relaxation strengthened with valid knapsack-cover inequalities. We then show that as we move away from global connectivity, the single pair case (that is, when only one pair (s,t) has positive connectivity requirement) captures much of the difficulty of Cap-SNDP: even strengthened with KC inequalities, the LP has an Ω(n) integrality gap. Furthermore, in directed graphs, we show that single pair Cap-SNDP is 2log 1-δ n-hard to approximate for any fixed constant δ>0. We also consider a variant of the Cap-SNDP in which multiple copies of an edge can be bought: we give an O(logk) approximation for this case, where k is the number of vertex pairs with non-zero connectivity requirement. This improves upon the previously known O( min {k, logR max })-approximation for this problem when the largest minimum-cut requirement, namely Rmax , is large. On the other hand, we observe that the multiple copy version of Cap-SNDP is Ω(log log n)-hard to approximate even for the single-source version of the problem.

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatoral Optimization - 15th International Conference, IPCO 2011, Proceedings
Pages78-91
Number of pages14
DOIs
StatePublished - 2011
Event15th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2011 - New York, NY, United States
Duration: Jun 15 2011Jun 17 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6655 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other15th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2011
CountryUnited States
CityNew York, NY
Period6/15/116/17/11

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Approximability of capacitated network design'. Together they form a unique fingerprint.

  • Cite this

    Chakrabarty, D., Chekuri, C., Khanna, S., & Korula, N. (2011). Approximability of capacitated network design. In Integer Programming and Combinatoral Optimization - 15th International Conference, IPCO 2011, Proceedings (pp. 78-91). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6655 LNCS). https://doi.org/10.1007/978-3-642-20807-2_7