Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
From MaRDI portal
Publication:3158519
DOI10.1145/290179.290180zbMath1064.90566OpenAlexW2165142526WikidataQ55870928 ScholiaQ55870928MaRDI QIDQ3158519
Publication date: 25 January 2005
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.7421
Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items
Improved approximation algorithms for single-tiered relay placement ⋮ Faster algorithms for orienteering and \(k\)-TSP ⋮ Quasilinear approximation scheme for Steiner multi cycle in the Euclidean plane ⋮ Bottleneck bichromatic full Steiner trees ⋮ Approximation algorithms for the TSP with sharpened triangle inequality ⋮ On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem ⋮ Optimal relay node placement in delay constrained wireless sensor network design ⋮ Hard constraint satisfaction problems have hard gaps at location 1 ⋮ 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 ⋮ Approximability of the minimum-weight \(k\)-size cycle cover problem ⋮ Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane ⋮ Improved approximation algorithms for some min-max and minimum cycle cover problems ⋮ Constant factor approximation algorithm for TSP satisfying a biased triangle inequality ⋮ Approximation schemes for Euclidean vehicle routing problems with time windows ⋮ Efficient PTAS for the maximum traveling salesman problem in a metric space of fixed doubling dimension ⋮ The simultaneous semi-random model for TSP ⋮ Improved approximations for capacitated vehicle routing with unsplittable client demands ⋮ Polynomial time approximation schemes and parameterized complexity ⋮ Reducing the size of combinatorial optimization problems using the operator vaccine by fuzzy selector with adaptive heuristics ⋮ Budget constrained minimum cost connected medians ⋮ The parameterized complexity of local search for TSP, more refined ⋮ Approximability of the vehicle routing problem in finite-dimensional Euclidean spaces ⋮ Improved approximation algorithms for cumulative VRP with stochastic demands ⋮ The generalized definitions of the two-dimensional largest common substructure problems ⋮ The traveling salesman problem on grids with forbidden neighborhoods ⋮ On global integer extrema of real-valued box-constrained multivariate quadratic functions ⋮ On the area requirements of Euclidean minimum spanning trees ⋮ On approximating string selection problems with outliers ⋮ Polynomial-time approximation scheme for the capacitated vehicle routing problem with time windows ⋮ On the approximability of dense Steiner problems ⋮ Exponential approximation schemata for some network design problems ⋮ Computing the variance of tour costs over the solution space of the TSP in polynomial time ⋮ Randomized approximation scheme for Steiner multi cycle in the Euclidean plane ⋮ Group sweep coverage with guaranteed approximation ratio ⋮ A PTAS for weight constrained Steiner trees in series--parallel graphs. ⋮ A convex approach to the Gilbert-Steiner problem ⋮ Colored spanning graphs for set visualization ⋮ Near-linear-time deterministic plane Steiner spanners for well-spaced point sets ⋮ The traveling salesman problem with flexible coloring ⋮ Approximation algorithms for maximum independent set of pseudo-disks ⋮ Shifting strategy for geometric graphs without geometry ⋮ Approximating the metric TSP in linear time ⋮ The saga of minimum spanning trees ⋮ Not being (super)thin or solid is hard: A study of grid Hamiltonicity ⋮ Polynomial area bounds for MST embeddings of trees ⋮ The Steiner ratio of high-dimensional Banach--Minkowski spaces. ⋮ Optimizing flight trajectory of UAV for efficient data collection in wireless sensor networks ⋮ Memetic algorithm based on improved inver-over operator and Lin-Kernighan local search for the Euclidean traveling salesman problem ⋮ \(\boldsymbol{borealis}\) -- a generalized global update algorithm for Boolean optimization problems ⋮ A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph ⋮ Approximability of the problem about a minimum-weight cycle cover of a graph ⋮ A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing ⋮ An improved algorithm for the Steiner tree problem with bounded edge-length ⋮ Approximation schemes for the generalized traveling salesman problem ⋮ A linearithmic heuristic for the travelling salesman problem ⋮ An improved algorithm for computing Steiner minimal trees in Euclidean \(d\)-space ⋮ Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension ⋮ Bounded-angle spanning tree: modeling networks with angular constraints ⋮ Hard to solve instances of the Euclidean traveling salesman problem ⋮ A novel feature-based approach to characterize algorithm performance for the traveling salesperson problem ⋮ On the history of the Euclidean Steiner tree problem ⋮ Steiner trees with bounded RC-delay ⋮ Bottleneck Steiner tree with bounded number of Steiner vertices ⋮ Approximating \(k\)-hop minimum spanning trees in Euclidean metrics ⋮ Shape rectangularization problems in intensity-modulated radiation therapy ⋮ The effect of the asymmetry of road transportation networks on the traveling salesman problem ⋮ The Euclidean bottleneck full Steiner tree problem ⋮ On Euclidean vehicle routing with allocation ⋮ A near linear time approximation scheme for Steiner tree among obstacles in the plane ⋮ The complexity of base station positioning in cellular networks ⋮ Cooperative TSP ⋮ Minimum weight connectivity augmentation for planar straight-line graphs ⋮ Structural and algorithmic properties for parametric minimum cuts ⋮ Traveling salesman problem across well-connected cities and with location-dependent edge lengths ⋮ Clique clustering yields a PTAS for max-coloring interval graphs ⋮ Shortest Dubins paths through three points ⋮ Region-restricted clustering for geographic data mining ⋮ The frequency of the optimal Hamiltonian cycle computed with frequency quadrilaterals for traveling salesman problem ⋮ Degree bounded bottleneck spanning trees in three dimensions ⋮ Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem ⋮ A priori TSP in the scenario model ⋮ Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters ⋮ Efficient approximation of the metric CVRP in spaces of fixed doubling dimension ⋮ Approximation of the capacitated vehicle routing problem with a limited number of routes in metric spaces of fixed doubling dimension ⋮ Light orthogonal networks with constant geometric dilation ⋮ On the total perimeter of homothetic convex bodies in a convex container ⋮ Non-uniform packings ⋮ A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem ⋮ Degree-bounded minimum spanning trees ⋮ A randomized Delaunay triangulation heuristic for the Euclidean Steiner tree problem in \(\Re ^{d }\) ⋮ Bounded-angle minimum spanning trees ⋮ Approximating the minimum weight spanning tree of a set of points in the Hausdorff metric ⋮ Minimizing the sum of distances to a server in a constraint network ⋮ \(1\)-line minimum rectilinear Steiner trees and related problems ⋮ Approximation algorithms for some extensions of the maximum profit routing problem ⋮ Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem. ⋮ Makespan trade-offs for visiting triangle edges (extended abstract) ⋮ Competitive on-line coverage of grid environments by a mobile robot ⋮ PTAS for densest \(k\)-subgraph in interval graphs ⋮ Improved Lower Bounds on the Approximability of the Traveling Salesman Problem ⋮ On Locality-Sensitive Orderings and Their Applications ⋮ Two-level rectilinear Steiner trees ⋮ 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 ⋮ Consensus Patterns (Probably) Has no EPTAS ⋮ Approximation algorithms and heuristics for a 2-depot, heterogeneous Hamiltonian path problem ⋮ Steiner Trees with Bounded RC-Delay ⋮ HARDNESS AND APPROXIMATION OF OCTILINEAR STEINER TREES ⋮ Approximating the Metric TSP in Linear Time ⋮ Approximation Algorithms for Buy-at-Bulk Geometric Network Design ⋮ Good triangulations yield good tours ⋮ Euclidean Networks with a Backbone and a Limit Theorem for Minimum Spanning Caterpillars ⋮ TRAVELING SALESMAN PROBLEM OF SEGMENTS ⋮ Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing Problem ⋮ Approximation schemes for node-weighted geometric Steiner tree problems ⋮ Computing optimal Steiner trees in polynomial space ⋮ Variational Approximation of Functionals Defined on 1-dimensional Connected Sets: The Planar Case ⋮ Improved Approximation Algorithms for Min-Max and Minimum Vehicle Routing Problems ⋮ An exact algorithm with linear complexity for a problem of visiting megalopolises ⋮ A PTAS for MIN-\(k\)-SCCP in Euclidean space of arbitrary fixed dimension ⋮ Approximate Euclidean Steiner trees ⋮ A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem ⋮ Geometric planar networks on bichromatic collinear points ⋮ The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem ⋮ A PTAS for the geometric connected facility location problem ⋮ Motion planning algorithms for the Dubins Travelling Salesperson Problem ⋮ Approximating Airports and Railways ⋮ A Quasi-polynomial Time Approximation Scheme for Euclidean CVRPTW ⋮ Cubic TSP: A 1.3-Approximation ⋮ Vehicle routing on road networks: how good is Euclidean approximation? ⋮ Stochastic runtime analysis of a cross-entropy algorithm for traveling salesman problems ⋮ The traveling salesman theorem for Jordan curves ⋮ APPROXIMATION ALGORITHMS FOR BUY-AT-BULK GEOMETRIC NETWORK DESIGN ⋮ Sufficient and necessary conditions for an edge in the optimal Hamiltonian cycle based on frequency quadrilaterals ⋮ Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension ⋮ Iterated tour partitioning for Euclidean capacitated vehicle routing ⋮ An LP-based approximation algorithm for the generalized traveling salesman path problem ⋮ Approximations for the Steiner multicycle problem ⋮ A 3/4 differential approximation algorithm for traveling salesman problem ⋮ The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem ⋮ Unnamed Item ⋮ Euclidean prize-collecting Steiner forest ⋮ Constant-Factor Approximation for TSP with Disks ⋮ Unnamed Item ⋮ The Shortest Separating Cycle Problem ⋮ A priori TSP in the Scenario Model ⋮ Parameterized study of Steiner tree on unit disk graphs ⋮ Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP ⋮ Complexity and approximation for traveling salesman problems with profits ⋮ A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs ⋮ A PTAS for the Steiner Forest Problem in Doubling Metrics ⋮ Faster Steiner Tree Computation in Polynomial-Space ⋮ Routing vehicles to minimize fuel consumption ⋮ Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP ⋮ Limitations of VCG-based mechanisms ⋮ An Efficient Approximation Algorithm for the Steiner Tree Problem ⋮ Self-organizing maps in evolutionary approach for the traveling salesman problem and vehicle routing problem with time windows ⋮ Local Search Yields a PTAS for $k$-Means in Doubling Metrics ⋮ Improved Approximations for Hard Optimization Problems via Problem Instance Classification ⋮ A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals ⋮ On Locality-Sensitive Orderings and Their Applications ⋮ Capacitated Vehicle Routing with Non-uniform Speeds ⋮ Preconditioning for the Geometric Transportation Problem ⋮ Approximation Schemes for Capacitated Geometric Network Design ⋮ Clique Clustering Yields a PTAS for max-Coloring Interval Graphs ⋮ An improved upper bound for the TSP in cubic 3-edge-connected graphs ⋮ The local Steiner problem in normed planes ⋮ Statistical mechanics methods and phase transitions in optimization problems ⋮ Approximation Algorithms for Cumulative VRP with Stochastic Demands ⋮ Pricing on Paths: A PTAS for the Highway Problem ⋮ Approximating minimum Steiner point trees in Minkowski planes ⋮ 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 ⋮ Probabilistic Analysis of the Degree Bounded Minimum Spanning Tree Problem ⋮ The balanced connected subgraph problem ⋮ A domination algorithm for {0,1}-instances of the travelling salesman problem ⋮ Nonoblivious 2-Opt heuristics for the traveling salesman problem ⋮ Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency ⋮ 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 ⋮ Unnamed Item ⋮ Continuous reformulations and heuristics for the Euclidean travelling salesperson problem ⋮ Multi-level Steiner Trees ⋮ An Improved Strategy for Exploring a Grid Polygon ⋮ Min-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio ⋮ Improving TSP Tours Using Dynamic Programming over Tree Decompositions. ⋮ Efficient algorithms for online decision problems ⋮ Improved approximations for ordered TSP on near-metric graphs ⋮ Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems ⋮ Probabilistic \(k\)-median clustering in data streams ⋮ On minimum- and maximum-weight minimum spanning trees with neighborhoods ⋮ The traveling salesman problem with few inner points ⋮ Non-crossing geometric steiner arborescences ⋮ Approximation Schemes for Capacitated Geometric Network Design ⋮ Multi-Level Steiner Trees. ⋮ An ETH-Tight Exact Algorithm for Euclidean TSP ⋮ A Modern View on Stability of Approximation ⋮ Observation routes and external watchman routes ⋮ Time complexity of the analyst's traveling salesman algorithm ⋮ Unnamed Item
Uses Software
