科研之友
微信
新浪微博
Facebook
分享链接
摘要
Given a graph H = (V, F) with edge weights {w(e) : e is an element of F}, the weighted degree of a node v in H is Sigma{w(vu): vu is an element of F}. 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 Ice : e E E) and edge-weights {we : e E E), an intersecting supermodular set-function f on V. and degree bounds {b(v) : v B c 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 C V) of G with weighted degrees <= b(v). Our algorithm computes a solution of cost <= 2. opt, so that the weighted degree of every v E V 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 left perpendiculark/36right perpendicular. 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 v is an element of V is at most b(v) + 3, improving over the approximation b(v) + 4 of Bansal et al. (2008) [2].
- 出版日期2011-3-4
