skip to main content
10.1145/1250790.1250887acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article

Approximating minimum bounded degree spanning trees to within one of optimal

Published: 11 June 2007 Publication History

Abstract

In the Minimum Bounded Degree Spanning Tree problem, we aregiven an undirected graph with a degree upper bound Bv on eachvertex v, and the task is to find a spanning tree of minimumcost which satisfies all the degree bounds. Let OPT be the costof an optimal solution to this problem. In this paper, we presenta polynomial time algorithm which returns a spanning tree T ofcost at most OPT and dT(v) ≤ Bv+1 for all v, where dT(v) denotes the degree of v in T. This generalizes aresult of Furer and Raghavachari [8] to weighted graphs, andsettles a 15-year-old conjecture of Goemans [10] affirmatively. The algorithm generalizes when each vertex v hasa degree lower bound Av and a degree upper bound Bv, andreturns a spanning tree with cost at most OPT and Av - 1 ≤dT(v) ≤ Bv + 1 for all v. This is essentially the bestpossible. The main technique used is an extension of the iterativerounding method introduced by Jain [12] for the design ofapproximation algorithms.

References

[1]
K. Chaudhuri, S. Rao, S. Riesenfeld, and K. Talwar, What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs, In Proceedings of 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 26--39, 2005.
[2]
K. Chaudhuri, S. Rao, S. Riesenfeld, and K. Talwar. Push relabel and an improved approximation algorithm for the bounded-degree mst problem, In Proceedings of 33th International Colloquium on Automata, Languages and Programming, 2006.
[3]
William H. Cunningham, Testing membership in matroid polyhedra, Journal of Combinatorial Theory, Series B 36(2): 161--188, 1984.
[4]
J. Cheriyan, S. Vempala and A. Vetta, Network design via iterative rounding of setpair relaxations, Combinatorica 26(3) pp. 255--275, 2006.
[5]
G. Cornuejols, D. Naddef and J. Fonlupt The Traveling Salesman Problem on a Graph and some related Integer Polyhedra, Mathematical Programming, 33, pp. 1--27, 1985.
[6]
J. Edmonds, Matroids and the Greedy Algorithm. Mathematical Programming, 1:125--136, 1971.
[7]
L. Fleischer, K. Jain and D.PWilliamson, Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems., J. Comput. Syst. Sci. 72:5, 2006.
[8]
M. Förer and B. Raghavachari, Approximating the minimum-degree Steiner tree to within one of optimal, J. of Algorithms 17(3):409--423, 1994.
[9]
M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, USA, 1979.
[10]
M.X. Goemans, Minimum Bounded-Degree Spanning Trees, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 273--282, 2006.
[11]
D.S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, USA, 1997.
[12]
K. Jain, A factor 2 approximation algorithm for the generalized Steiner network problem, Combinatorica, 21, pp.39--60, 2001.
[13]
J. Könemann and R. Ravi, A matter of degree: Improved approximation algorithms for degree bounded minimum spanning trees, SIAM J. on Computing, 31:1783--1793, 2002.
[14]
J. Könemann and R. Ravi, Primal-Dual meets local search: approximating MSTs with nonuniform degree bounds, SIAM J. on Computing, 34(3):763--773, 2005.
[15]
L.C. Lau, S. Naor, M. Salavatipour and M. Singh, Survivable network design with degree or order constraints, in Proceedings of the 39th ACM Symposium on Theory of Computing, 2007.
[16]
T. Magnanti, L. Wolsey, Optimal trees, Network Models, Handbook in Operations Research and Management Science, M.O. Ball et al ed., Amsterdam, North-Holland, pp: 503--615, 1995.
[17]
V. Melkonian and E. Tardos, Algorithms for a Network Design Problem with Crossing Supermodular Demands, Networks, 43(4):256--265, 2004.
[18]
R. Ravi, M.V. Marathe, S.S. Ravi, D.J. Rosenkrants, and H.B. Hunt, Many birds with one stone: Multi-objective approximation algorithms, in Proceedings of the 25th ACM-Symposium on Theory of Computing, pp 438--447, 1993.
[19]
R. Ravi and M. Singh, Delegate and Conquer: An LP-based approximation algorithm for Minimum Degree MSTs. In Proceedings of 33rd International Colloquium on Automata, Languages and Programming, 2006.
[20]
A. Schrijver, Combinatorial Optimization - Polyhedra and Efficiency, Springer-Verlag, New York, 2005.
[21]
V. Vazirani, Approximation Algorithms, Springer, 2001.

Cited By

View all
  • (2024)Degree-Constrained Minimum Spanning Hierarchies in GraphsAlgorithms10.3390/a1710046717:10(467)Online publication date: 21-Oct-2024
  • (2024)Fast Combinatorial Algorithms for Efficient SortationInteger Programming and Combinatorial Optimization10.1007/978-3-031-59835-7_31(418-432)Online publication date: 22-May-2024
  • (2022)Bounded-degree rooted tree and TDI-nessRAIRO - Operations Research10.1051/ro/202210156:4(2181-2201)Online publication date: 20-Jul-2022
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing
June 2007
734 pages
ISBN:9781595936318
DOI:10.1145/1250790
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. approximation algorithm
  2. bounded degree
  3. iterative rounding
  4. spanning trees

Qualifiers

  • Article

Conference

STOC07
Sponsor:
STOC07: Symposium on Theory of Computing
June 11 - 13, 2007
California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25
57th Annual ACM Symposium on Theory of Computing (STOC 2025)
June 23 - 27, 2025
Prague , Czech Republic

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)7
  • Downloads (Last 6 weeks)0
Reflects downloads up to 17 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Degree-Constrained Minimum Spanning Hierarchies in GraphsAlgorithms10.3390/a1710046717:10(467)Online publication date: 21-Oct-2024
  • (2024)Fast Combinatorial Algorithms for Efficient SortationInteger Programming and Combinatorial Optimization10.1007/978-3-031-59835-7_31(418-432)Online publication date: 22-May-2024
  • (2022)Bounded-degree rooted tree and TDI-nessRAIRO - Operations Research10.1051/ro/202210156:4(2181-2201)Online publication date: 20-Jul-2022
  • (2020)Near-Linear Time Algorithm for Approximate Minimum Degree Spanning TreesLATIN 2020: Theoretical Informatics10.1007/978-3-030-61792-9_2(15-26)Online publication date: 3-Dec-2020
  • (2019)A new dynamic programming approach for spanning trees with chain constraints and beyondProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310529(1550-1569)Online publication date: 6-Jan-2019
  • (2019)On a generalization of iterated and randomized roundingProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316313(1125-1135)Online publication date: 23-Jun-2019
  • (2019)Approximate Multi-matroid Intersection via Iterative RefinementInteger Programming and Combinatorial Optimization10.1007/978-3-030-17953-3_23(299-312)Online publication date: 13-Apr-2019
  • (2018)k-TrailsMathematical Programming: Series A and B10.5555/3288898.3288952172:1-2(169-189)Online publication date: 1-Nov-2018
  • (2018)Approximating min-cost chain-constrained spanning treesMathematical Programming: Series A and B10.5555/3288898.3288947172:1-2(17-34)Online publication date: 1-Nov-2018
  • (2018)1-Skeletons of the Spanning Tree Problems with Additional ConstraintsAutomatic Control and Computer Sciences10.3103/S014641161707003351:7(682-688)Online publication date: 7-Feb-2018
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media