Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
From MaRDI portal
Publication:3158519
DOI10.1145/290179.290180zbMath1064.90566DBLPjournals/jacm/Arora98OpenAlexW2165142526WikidataQ55870928 ScholiaQ55870928MaRDI QIDQ3158519
No author found.
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 (only showing first 100 items - show all)
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. ⋮ Improved approximation algorithms for single-tiered relay placement
Uses Software
This page was built for publication: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
