Additive guarantees for degree bounded directed network design

N. Bansal, R. Khandekar, V. Nagarajan

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    22 Citaten (Scopus)


    We present polynomial-time approximation algorithms for some degree-bounded directed network design problems. Our main result is for intersecting supermodular connectivity with degree bounds: given a directed graph G=(V,E) with non-negative edge-costs, a connectivity requirement specified by an intersecting supermodular function f, and upper bounds av, bvv¿ 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 that for any 0 = e = 1/2, computes an f-connected subgraph with in-degrees at most ¿ av/1-e ¿ + 4, out-degrees at most ¿ bv/1-e ¿ + 4, and cost at most 1/e times the optimum. This includes, as a special case, the minimum-cost degree-bounded arborescence problem. We also obtain similar results for the (more general) class of crossing supermodular requirements. Our result extends and improves the (3av+4, 3bv+4, 3)-approximation of Lau et al. Setting e=0, our result gives the first purely additive guarantee for the unweighted versions of these problems. Our algorithm is based on rounding an LP relaxation for the problem. We also prove that the above cost-degree trade-off (even for the degree-bounded arborescence problem) is optimal relative to the natural LP relaxation. For every 0
    Originele taal-2Engels
    TitelProceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC'08, Victoria BC, Canada, May 17-20, 2008)
    Plaats van productieNew York
    UitgeverijAssociation for Computing Machinery, Inc
    ISBN van geprinte versie978-1-60558-047-0
    StatusGepubliceerd - 2008

    Vingerafdruk Duik in de onderzoeksthema's van 'Additive guarantees for degree bounded directed network design'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit