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

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

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