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

DOI10.1137/S0097539796303299zbMATH Open0918.68045OpenAlexW2017698201MaRDI QIDQ4229405FDOQ4229405

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

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

zbMATH Keywords

dynamic programmingcomputational geometrynetwork optimizationminimum spanning treesguillotine subdivisions\(k\)-MSTguillotineapproximation algorithms polynomialbank robber (orienteering) problemprize-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)

Cited In (4)

• A constant-factor approximation algorithm for the \(k\)-MST problem
• Title not available (Why is that?)
• On the minimum corridor connection problem and other generalized geometric problems
• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints

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)