Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
From MaRDI portal
approximation algorithmsbicriteria approximationdegree-bounded spanning treesLagrangian relaxationnetwork algorithmsspanning trees
Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)
Recommendations
- Primal-dual meets local search: approximating MST's with nonuniform degree bounds
- A matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees
- A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
- What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
Cited in
(21)- 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
- What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs
- An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem
- A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
- A matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees
- A 2k-vertex kernel for maximum internal spanning tree
- Multi-objective Problems in Terms of Relational Algebra
- Primal-dual meets local search: approximating MST's with nonuniform degree bounds
- Network Design with Weighted Degree Constraints
- Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs
- Network design with weighted degree constraints
- Budgeted matching and budgeted matroid intersection via the gasoline puzzle
- Approximating minimum bounded degree spanning trees to within one of optimal
- On approximating degree-bounded network design problems
- Fast combinatorial algorithms for efficient sortation
- Fast combinatorial algorithms for efficient sortation
- Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree
This page was built for publication: Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5317173)
