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

DOI10.1137/S0097539702418048zbMath1075.68101MaRDI 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 relaxation; approximation algorithms; network algorithms; spanning trees; bicriteria approximation; degree-bounded spanning trees

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

05C05: Trees

68R10: Graph theory (including graph drawing) in computer science

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

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