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

DOI10.1137/S0097539796309764zbMath0940.68062DBLPjournals/siamcomp/Mitchell99WikidataQ55880291 ScholiaQ55880291MaRDI QIDQ4268710

Joseph S. B. Mitchell

Publication date: 28 October 1999

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

zbMATH Keywords

computational geometryapproximation algorithmsSteiner minimal treespolynomial-time approximation schemetraveling salesperson problemguillotine subdivisions\(k\)-MST

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 (98)

Improved Lower Bounds on the Approximability of the Traveling Salesman Problem ⋮ Faster algorithms for orienteering and \(k\)-TSP ⋮ Performance guarantees for the TSP with a parameterized triangle inequality ⋮ A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs ⋮ Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic ⋮ HARDNESS AND APPROXIMATION OF OCTILINEAR STEINER TREES ⋮ The number of guillotine partitions in \(d\) dimensions ⋮ A linear time algorithm for max-min length triangulation of a convex polygon ⋮ On a new edge function on complete weighted graphs and its application for locating Hamiltonian cycles of small weight ⋮ Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing ⋮ BALANCED PARTITION OF MINIMUM SPANNING TREES ⋮ TRAVELING SALESMAN PROBLEM OF SEGMENTS ⋮ Approximation schemes for node-weighted geometric Steiner tree problems ⋮ Constant factor approximation algorithm for TSP satisfying a biased triangle inequality ⋮ A PTAS for MIN-\(k\)-SCCP in Euclidean space of arbitrary fixed dimension ⋮ Efficient PTAS for the maximum traveling salesman problem in a metric space of fixed doubling dimension ⋮ Approximate Euclidean Steiner trees ⋮ A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem ⋮ Submodularity and the traveling salesman problem ⋮ The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem ⋮ A PTAS for the geometric connected facility location problem ⋮ Improved approximation algorithms for cumulative VRP with stochastic demands ⋮ On the area requirements of Euclidean minimum spanning trees ⋮ The traveling salesman theorem for Jordan curves ⋮ Cut equivalence of \(d\)-dimensional guillotine partitions ⋮ APPROXIMATION ALGORITHMS FOR BUY-AT-BULK GEOMETRIC NETWORK DESIGN ⋮ Rectangular partitions of a rectilinear polygon ⋮ Iterated tour partitioning for Euclidean capacitated vehicle routing ⋮ On the longest flip sequence to untangle segments in the plane ⋮ A 3/4 differential approximation algorithm for traveling salesman problem ⋮ The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem ⋮ An ETH-Tight Exact Algorithm for Euclidean TSP ⋮ An Approximation Algorithm for the Continuous k-Medians Problem in a Convex Polygon ⋮ Observation routes and external watchman routes ⋮ Euclidean prize-collecting Steiner forest ⋮ Connecting a set of circles with minimum sum of radii ⋮ Colored spanning graphs for set visualization ⋮ Time complexity of the analyst's traveling salesman algorithm ⋮ Constant-Factor Approximation for TSP with Disks ⋮ Near-linear-time deterministic plane Steiner spanners for well-spaced point sets ⋮ The Shortest Separating Cycle Problem ⋮ Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP ⋮ A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs ⋮ Minimum covering with travel cost ⋮ Unnamed Item ⋮ A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics ⋮ Not being (super)thin or solid is hard: A study of grid Hamiltonicity ⋮ A survey on relay placement with runtime and approximation guarantees ⋮ Polynomial area bounds for MST embeddings of trees ⋮ Routing vehicles to minimize fuel consumption ⋮ A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing ⋮ A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals ⋮ The capacitated orienteering problem ⋮ Capacitated Vehicle Routing with Non-uniform Speeds ⋮ Approximation Schemes for Capacitated Geometric Network Design ⋮ Bounded-angle spanning tree: modeling networks with angular constraints ⋮ Delineating boundaries for imprecise regions ⋮ APPROXIMATING ASYMMETRIC TSP IN EXPONENTIAL TIME ⋮ Shape rectangularization problems in intensity-modulated radiation therapy ⋮ An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints ⋮ A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem ⋮ On Euclidean vehicle routing with allocation ⋮ A near linear time approximation scheme for Steiner tree among obstacles in the plane ⋮ Cooperative TSP ⋮ On the number of rectangulations of a planar point set ⋮ APPROXIMATION ALGORITHM FOR MULTIPLE-TOOL MILLING ⋮ Polygons cuttable by a circular saw ⋮ Polychromatic 4-coloring of guillotine subdivisions ⋮ Algorithms for Euclidean Degree Bounded Spanning Tree Problems ⋮ Approximation Algorithms for Cumulative VRP with Stochastic Demands ⋮ Capacitated Vehicle Routing with Nonuniform Speeds ⋮ Maximum bipartite matchings with low rank data: locality and perturbation analysis ⋮ PTAS FOR k-TOUR COVER PROBLEM ON THE PLANE FOR MODERATELY LARGE VALUES OF k ⋮ Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem ⋮ Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem ⋮ Approximation algorithms for the load-balanced capacitated vehicle routing problem ⋮ Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters ⋮ A domination algorithm for {0,1}-instances of the travelling salesman problem ⋮ Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency ⋮ Local search algorithms for the \(k\)-cardinality tree problem. ⋮ The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme ⋮ Travelling on graphs with small highway dimension ⋮ Exploring and Triangulating a Region by a Swarm of Robots ⋮ APPROXIMATION ALGORITHMS FOR THE EUCLIDEAN TRAVELING SALESMAN PROBLEM WITH DISCRETE AND CONTINUOUS NEIGHBORHOODS ⋮ Differential approximation of NP-hard problems with equal size feasible solutions ⋮ Unnamed Item ⋮ Degree-bounded minimum spanning trees ⋮ Multi-level Steiner Trees ⋮ Unnamed Item ⋮ An Improved Strategy for Exploring a Grid Polygon ⋮ Approximating the minimum weight spanning tree of a set of points in the Hausdorff metric ⋮ Approximation algorithms for lawn mowing and milling ⋮ Bounded queries, approximations, and the Boolean hierarchy ⋮ The traveling salesman problem with few inner points ⋮ Approximation Schemes for Capacitated Geometric Network Design ⋮ Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem. ⋮ Multi-Level Steiner Trees. ⋮ Competitive on-line coverage of grid environments by a mobile robot

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