Approximate integer decompositions for undirected network design problems

Chandra Chekuri, F. Bruce Shepherd

Research output: Contribution to journalArticle

Abstract

A well-known theorem of Nash-Williams and Tutte gives a necessary and sufficient condition for the existence of k edge-disjoint spanning trees in an undirected graph. A corollary of this theorem is that every 2k-edge-connected graph has k edge-disjoint spanning trees. We show that the splitting-off theorem of Mader in undirected graphs implies a generalization of this to finding k edge-disjoint Steiner forests in Eulerian graphs. This leads to new 2-approximation rounding algorithms for certain constrained 0-1 forest problems considered by Goemans andWilliamson. These algorithms also produce approximate integer decompositions of fractional solutions. We then discuss open problems and outlets for this approach to the more general class of 0-1 skew supermodular network design problems.

Original languageEnglish (US)
Pages (from-to)163-177
Number of pages15
JournalSIAM Journal on Discrete Mathematics
Volume23
Issue number1
DOIs
StatePublished - Dec 1 2008

Keywords

  • Approximation algorithm
  • Integer decomposition
  • Network design
  • Supermodular function

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Approximate integer decompositions for undirected network design problems'. Together they form a unique fingerprint.

  • Cite this