A constant-factor approximation algorithm for the \(k\)-MST problem

DOI10.1006/jcss.1997.1542zbMath0946.68109OpenAlexW1575625195MaRDI QIDQ1305925

R. Ravi, Santosh Vempala, Avrim L. Blum

Publication date: 17 February 2000

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1997.1542

zbMATH Keywords

undirected graph

Mathematics Subject Classification ID

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

Related Items (13)

Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing ⋮ On the Integrality Gap of the Prize-Collecting Steiner Forest LP ⋮ Algorithms for the Maximum Weight Connected $$k$$-Induced Subgraph Problem ⋮ A 4-approximation algorithm for \(k\)-prize collecting Steiner tree problems ⋮ Pruning 2-connected graphs ⋮ Euclidean prize-collecting Steiner forest ⋮ Complexity and approximation for traveling salesman problems with profits ⋮ An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints ⋮ A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem ⋮ Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph ⋮ Local search algorithms for the \(k\)-cardinality tree problem. ⋮ A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs ⋮ A 2-approximation for the \(k\)-prize-collecting Steiner tree problem

Cites Work

• The minimum latency problem
• The orienteering problem
• The prize collecting traveling salesman problem
• Weighted k‐cardinality trees: Complexity and polyhedral structure
• A General Approximation Technique for Constrained Forest Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A constant-factor approximation algorithm for the \(k\)-MST problem