Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds

DOI10.1137/S0097539702418048zbMath1075.68101OpenAlexW1975884818MaRDI QIDQ5317173

Jochen Könemann, R. Ravi

Publication date: 16 September 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539702418048

zbMATH Keywords

Lagrangian relaxationapproximation algorithmsnetwork algorithmsspanning treesbicriteria approximationdegree-bounded spanning trees

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (15)

On approximating degree-bounded network design problems ⋮ A 2k-vertex Kernel for Maximum Internal Spanning Tree ⋮ On generalizations of network design problems with degree bounds ⋮ The \((K, k)\)-capacitated spanning tree problem ⋮ Multi-objective Problems in Terms of Relational Algebra ⋮ Network design with weighted degree constraints ⋮ Bounded-degree light approximate shortest-path trees in doubling metrics ⋮ An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem ⋮ Budgeted matching and budgeted matroid intersection via the gasoline puzzle ⋮ On approximating degree-bounded network design problems ⋮ Network Design with Weighted Degree Constraints ⋮ Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree ⋮ The maximum binary tree problem ⋮ Degree-bounded minimum spanning trees ⋮ Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal

This page was built for publication: Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds