Additive guarantees for degree-bounded directed network design

N. Bansal, R. Khandekar, V. Nagarajan

    Research output: Contribution to journalArticleAcademicpeer-review

    39 Citations (Scopus)
    134 Downloads (Pure)

    Abstract

    We present polynomial-time approximation algorithms for some degree-bounded directed network design problems. Our main result is for intersecting supermodular connectivity requirements with degree bounds: given a directed graph $G=(V,E)$ with nonnegative edge-costs, a connectivity requirement specified by an intersecting supermodular function $f$, and upper bounds $\{a_v,b_v\}_{v\in V}$ on in-degrees and out-degrees of vertices, find a minimum-cost $f$-connected subgraph of $G$ that satisfies the degree bounds. We give a bicriteria approximation algorithm for this problem using the natural LP relaxation and show that our guarantee is the best possible relative to this LP relaxation. We also obtain similar results for the (more general) class of crossing supermodular requirements. In the absence of edge-costs, our result gives the first additive $O(1)$-approximation guarantee for degree-bounded intersecting/crossing supermodular connectivity problems. We also consider the minimum crossing spanning tree problem: Given an undirected edge-weighted graph $G$, edge-subsets $\{E_i\}_{i=1}^k$, and nonnegative integers $\{b_i\}_{i=1}^k$, find a minimum-cost spanning tree (if it exists) in $G$ that contains at most $b_i$ edges from each set $E_i$. We obtain a $+(r-1)$ additive approximation for this problem, when each edge lies in at most $r$ sets. A special case of this problem is the degree-bounded minimum spanning tree, and our techniques give a substantially shorter proof of the recent $+1$ approximation of Singh and Lau [in Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2007, pp. 661–670].
    Original languageEnglish
    Pages (from-to)1413-1431
    JournalSIAM Journal on Computing
    Volume39
    Issue number4
    DOIs
    Publication statusPublished - 2009

    Fingerprint

    Dive into the research topics of 'Additive guarantees for degree-bounded directed network design'. Together they form a unique fingerprint.

    Cite this