Abstract
Given a graph H = (V,F) with edge weights {w(e):e ∈ F}, the weighted degree of a node v in H is ∑ {w(vu):vu ∈ 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), edge-costs {c(e):e ∈ E}, edge-weights {w(e):e ∈ E}, an intersecting supermodular set-function f on V, and degree bounds {b(v):v ∈ 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 , so that the weighted degree of every v ∈ V is at most: 7 b(v) for arbitrary f and 5 b(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 and weighted degrees ≤ 6 b(v). We obtain similar results when there are both indegree and outdegree constraints, and better results when there are indegree constraints only: a (1,4)-approximation algorithm for arbitrary weights and a polynomial time algorithm for unit weights. Finally, we consider the problem of packing maximum number k of edge-disjoint arborescences so that their union satisfies weighted degree constraints, and give an algorithm that computes a solution of value at least \(\lfloor k/36 \rfloor\).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bang-Jensen, J., Thomassé, S., Yeo, A.: Small degree out-branchings. J. of Graph Theory 42(4), 287–307 (2003)
Bansal, N., Khandekar, R., Nagarajan, V.: Additive gurantees for degree bounded directed network design. In: STOC 2008, pp. 769–778 (2008)
Chaudhuri, K., Rao, S., Riesenfeld, S., Talwar, K.: A push-relabel algorithm for approximating degree bounded MSTs. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 191–201. Springer, Heidelberg (2006)
Frank, A.: Connectivity and network flows. In: Graham, R.L., Grötschel, M., Lovász, L. (eds.) Handbook of Combinatorics, ch. 2, pp. 111–177. Elsevier, Amsterdam (1995)
Fukunaga, T., Nagamochi, H.: Network design with weighted degree constraints. TR 2008-005, Kyoto University (manuscript, 2008)
Furer, M., Raghavachari, B.: Approximating the minimum-degree steiner tree to within one of optimal. Journal of Algorithms 17(3), 409–423 (1994)
Goemans, M.X.: Minimum bounded degree spanning trees. In: FOCS, pp. 273–282 (2006)
Goemans, M.X., Williamson, D.P.: The primal-dual method in approximation algorithms and its applications to network design problems. In: Hochbaum, D.S. (ed.) Approximation Algorithms For NP-hard Problems, ch. 4. PWS (1997)
Jain, K.: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21(1), 39–60 (2001)
Khuller, S.: Approximation algorithm for finding highly connected subgraphs. In: Hochbaum, D.S. (ed.) Approximation Algorithms For NP-hard Problems, ch. 6. PWS (1997)
Könemann, J., Ravi, R.: A matter of degree: Improved approximation algorithms for degree bounded minimum spanning trees. SIAM Journal on Computing 31(3), 1783–1793 (2002)
Kortsarz, G., Nutov, Z.: Approximating minimum-cost connectivity problems. In: Gonzalez, T.F. (ed.) Approximation Algorithms and Metaheuristics, ch. 58. Chapman & Hall/CRC, Boca Raton (2007)
Lau, L.C., Naor, J., Salavatipour, M.R., Singh, M.: Survivable network design with degree or order constraints. In: STOC, pp. 651–660 (2007)
Melkonian, V., Tardos, E.: Algorithms for a network design problem with crossing supermodular demands. Networks 43(4), 256–265 (2004)
Ravi, R., Marathe, M.V., Ravi, S.S., Rosenkrantz, D.J., Hunt III, H.B.: Many birds with one stone: Multi objective approximation algorithms. In: STOC, pp. 438–447 (1993)
Schrijver, A.: Combinatorial Optimization, Polyhedra and Efficiency. Springer, Heidelberg (2004)
Singh, M., Lau, L.C.: Approximating minimum bounded degree spanning trees to within one of optimal. In: STOC, pp. 661–670 (2007)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nutov, Z. (2008). Approximating Directed Weighted-Degree Constrained Networks. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds) Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2008 2008. Lecture Notes in Computer Science, vol 5171. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85363-3_18
Download citation
DOI: https://doi.org/10.1007/978-3-540-85363-3_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85362-6
Online ISBN: 978-3-540-85363-3
eBook Packages: Computer ScienceComputer Science (R0)