A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem

DOI10.1007/s10107-005-0693-1zbMath1111.90101OpenAlexW2012511041MaRDI QIDQ2492706

George Karakostas, Sanjeev Arora

Publication date: 14 June 2006

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-005-0693-1

zbMATH Keywords

Approximation algorithmPrimal-Dual schema

Mathematics Subject Classification ID

Nonlinear programming (90C30) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Approximation and complexity of multi-target graph search and the Canadian traveler problem ⋮ Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing ⋮ A 4-approximation algorithm for \(k\)-prize collecting Steiner tree problems ⋮ Multirobot search for a stationary object placed in a known environment with a combination of GRASP and VND ⋮ A unified approach to approximate partial, prize-collecting, and budgeted sweep cover problems ⋮ Complexity and approximation for traveling salesman problems with profits ⋮ Implicit branching and parameterized partial cover problems ⋮ Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints ⋮ Approximating node-weighted \(k\)-MST on planar graphs ⋮ On combining machine learning with decision making ⋮ An approximation algorithm for vehicle routing with compatibility constraints ⋮ A 2-approximation for the \(k\)-prize-collecting Steiner tree problem

Cites Work

• Unnamed Item
• Unnamed Item
• A 2.5-factor approximation algorithm for the \(k\)-MST problem
• An improved approximation ratio for the minimum latency problem
• A constant-factor approximation algorithm for the \(k\)-MST problem
• The minimum latency problem
• Saving an epsilon
• New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Weighted k‐cardinality trees: Complexity and polyhedral structure
• A General Approximation Technique for Constrained Forest Problems
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Spanning Trees—Short or Small