A Constant-Factor Approximation Algorithm for the Geometrick-MST Problem in the Plane

DOI10.1137/S0097539796303299MaRDI QIDQ4229405zbMATH OpenOpenAlexFDO

Authors Joseph S. B. Mitchell, Prasad Chalasani, Avrim Blum, Santosh S. Vempala

Publication date 22 February 1999

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

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

zbMATH Keywords

\(k\)-MSTapproximation algorithms polynomialbank robber (orienteering) problemcomputational geometrydynamic programmingguillotineguillotine subdivisionsminimum spanning treesnetwork optimizationprize-collecting salesman problemquota traveling salesman problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• scientific article; zbMATH DE number 871938
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• scientific article; zbMATH DE number 1263205
• A constant-factor approximation algorithm for the \(k\)-MST problem

Cited in

(8)

• A constant-factor approximation algorithm for the \(k\)-MST problem
• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
• scientific article; zbMATH DE number 1256763 (Why is no real title available?)
• scientific article; zbMATH DE number 1263205 (Why is no real title available?)
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• scientific article; zbMATH DE number 871938 (Why is no real title available?)
• Faster approximation scheme for Euclidean k-TSP
• On the minimum corridor connection problem and other generalized geometric problems

This page was built for publication: A Constant-Factor Approximation Algorithm for the Geometrick-MST Problem in the Plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4229405)