Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems

DOI10.1137/S0097539796309764zbMath0940.68062WikidataQ55880291 ScholiaQ55880291MaRDI QIDQ4268710

Publication date: 28 October 1999

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

computational geometry; approximation algorithms; Steiner minimal trees; polynomial-time approximation scheme; traveling salesperson problem; guillotine subdivisions; \(k\)-MST

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

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

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

Related Items

Differential approximation of NP-hard problems with equal size feasible solutions, Improved Lower Bounds on the Approximability of the Traveling Salesman Problem, APPROXIMATION ALGORITHM FOR MULTIPLE-TOOL MILLING, BALANCED PARTITION OF MINIMUM SPANNING TREES, TRAVELING SALESMAN PROBLEM OF SEGMENTS, HARDNESS AND APPROXIMATION OF OCTILINEAR STEINER TREES, Polygons cuttable by a circular saw, Shape rectangularization problems in intensity-modulated radiation therapy, The number of guillotine partitions in \(d\) dimensions, A linear time algorithm for max-min length triangulation of a convex polygon, Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing, Not being (super)thin or solid is hard: A study of grid Hamiltonicity, Cooperative TSP, Polychromatic 4-coloring of guillotine subdivisions, Degree-bounded minimum spanning trees, Approximating the minimum weight spanning tree of a set of points in the Hausdorff metric, Submodularity and the traveling salesman problem, Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem., Local search algorithms for the \(k\)-cardinality tree problem., Approximation algorithms for lawn mowing and milling, Bounded queries, approximations, and the Boolean hierarchy, Competitive on-line coverage of grid environments by a mobile robot, On Euclidean vehicle routing with allocation, A near linear time approximation scheme for Steiner tree among obstacles in the plane, Approximation schemes for node-weighted geometric Steiner tree problems, Delineating boundaries for imprecise regions, An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints, A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem, On the number of rectangulations of a planar point set, The traveling salesman problem with few inner points, Capacitated Vehicle Routing with Non-uniform Speeds, Approximation Schemes for Capacitated Geometric Network Design, PTAS FOR k-TOUR COVER PROBLEM ON THE PLANE FOR MODERATELY LARGE VALUES OF k, Exploring and Triangulating a Region by a Swarm of Robots, An Improved Strategy for Exploring a Grid Polygon, APPROXIMATION ALGORITHMS FOR THE EUCLIDEAN TRAVELING SALESMAN PROBLEM WITH DISCRETE AND CONTINUOUS NEIGHBORHOODS