TY - JOUR

T1 - Approximating directed weighted-degree constrained networks

AU - Nutov, Zeev

PY - 2011/3/4

Y1 - 2011/3/4

N2 - Given a graph H=(V,F) with edge weights we:eF, the weighted degree of a node v in H is ∑wvu:vuF. We give bicriteria approximation algorithms for problems that seek to find a minimum cost directed graph that satisfies both intersecting supermodular connectivity requirements and weighted degree constraints. The input to such problems is a directed graph G=(V,E) with edge-costs ce:eE and edge-weights we:eE, an intersecting supermodular set-function f on V, and degree bounds b(v):vB⊆V. The goal is to find a minimum cost f-connected subgraph H=(V,F) (namely, at least f(S) edges in F enter every S⊆V) of G with weighted degrees ≤b(v). Our algorithm computes a solution of cost ≤2·opt, so that the weighted degree of every vV is at most: 7b(v) for arbitrary f and 5b(v) for a 0,1-valued f; 2b(v)+4 for arbitrary f and 2b(v)+2 for a 0,1-valued f in the case of unit weights. Another algorithm computes a solution of cost ≤3·opt and weighted degrees ≤6b(v). We obtain similar results when there are both indegree and outdegree constraints, and better results when there are indegree constraints only: a (1,4b(v))-approximation algorithm for arbitrary weights and a polynomial time algorithm for unit weights. Similar results are shown for crossing supermodular f. We also consider the problem of packing maximum number k of pairwise edge-disjoint arborescences so that their union satisfies weighted degree constraints, and give an algorithm that computes a solution of value at least ⌊k36⌋. Finally, for unit weights and without trying to bound the cost, we give an algorithm that computes a subgraph so that the degree of every vV is at most b(v)+3, improving over the approximation b(v)+4 of Bansal et al. (2008) [2].

AB - Given a graph H=(V,F) with edge weights we:eF, the weighted degree of a node v in H is ∑wvu:vuF. We give bicriteria approximation algorithms for problems that seek to find a minimum cost directed graph that satisfies both intersecting supermodular connectivity requirements and weighted degree constraints. The input to such problems is a directed graph G=(V,E) with edge-costs ce:eE and edge-weights we:eE, an intersecting supermodular set-function f on V, and degree bounds b(v):vB⊆V. The goal is to find a minimum cost f-connected subgraph H=(V,F) (namely, at least f(S) edges in F enter every S⊆V) of G with weighted degrees ≤b(v). Our algorithm computes a solution of cost ≤2·opt, so that the weighted degree of every vV is at most: 7b(v) for arbitrary f and 5b(v) for a 0,1-valued f; 2b(v)+4 for arbitrary f and 2b(v)+2 for a 0,1-valued f in the case of unit weights. Another algorithm computes a solution of cost ≤3·opt and weighted degrees ≤6b(v). We obtain similar results when there are both indegree and outdegree constraints, and better results when there are indegree constraints only: a (1,4b(v))-approximation algorithm for arbitrary weights and a polynomial time algorithm for unit weights. Similar results are shown for crossing supermodular f. We also consider the problem of packing maximum number k of pairwise edge-disjoint arborescences so that their union satisfies weighted degree constraints, and give an algorithm that computes a solution of value at least ⌊k36⌋. Finally, for unit weights and without trying to bound the cost, we give an algorithm that computes a subgraph so that the degree of every vV is at most b(v)+3, improving over the approximation b(v)+4 of Bansal et al. (2008) [2].

KW - Bicriteria approximation algorithms

KW - Directed network design

KW - Intersecting supermodular requirements

KW - Weighted degree constraints

UR - http://www.scopus.com/inward/record.url?scp=79151477890&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2010.11.043

DO - 10.1016/j.tcs.2010.11.043

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:79151477890

SN - 0304-3975

VL - 412

SP - 901

EP - 912

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 8-10

ER -