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

DOI10.1137/S0097539796303299zbMath0918.68045OpenAlexW2017698201MaRDI QIDQ4229405

Joseph S. B. Mitchell, Prasad Chalasani, Avrim L. Blum, Santosh 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

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)

Related Items (1)

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