A Linear Time Approximation Scheme for Euclidean TSP

No abstract is available for this paper.

• Publication year

  2013

• Venue

  IEEE Annual Symposium on Foundations of Computer Science

• Publication date

  2013-10-26

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/FOCS.2013.80
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Traveling Salesman Problem and its Variations

  2014cited by this paper
• Approximating 1-dimensional TSP Requires Omega(n log n) Comparisons

  2013cited by this paper
• Near-linear-time deterministic plane Steiner spanners for well-spaced point sets

  2012cited by this paper
• The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme

  2011cited by this paper
• A QPTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling Metrics

  2010cited by this paper
• A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights

  2008cited by this paper
• Approximating TSP on metrics with bounded global growth

  2008cited by this paper
• Well-separated pair decomposition in linear time?

  2008cited by this paper
• The traveling salesman problem and its variations

  2007cited by this paper
• A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem

  2007cited by this paper
• The Traveling Salesman Problem: A Computational Study (Princeton Series in Applied Mathematics)

  2007cited by this paper
• A PTAS for TSP with neighborhoods among fat regions in the plane

  2007cited by this paper
• Searching dynamic point sets in spaces with bounded doubling dimension

  2006cited by this paper
• Deformable spanners and applications.

  2006cited by this paper
• Navigating nets: simple algorithms for proximity search

  2004cited by this paper
• Ordered theta graphs

  2004cited by this paper
• Bypassing the embedding: algorithms for low dimensional metrics

  2004cited by this paper
• A tight bound on approximating arbitrary metrics by tree metrics

  2003cited by this paper
• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners

  2002cited by this paper
• Polynomial-Time Approximation Schemes for the Euclidean Survivable Network Design Problem

  2002cited by this paper
• Approximating the Minimum Spanning Tree Weight in Sublinear Time

  2001cited by this paper
• When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree

  2000cited by this paper
• A Nearly Linear-Time Approximation Scheme for the Euclidean kappa-median Problem

  1999cited by this paper
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems

  1999cited by this paper
• A Polynomial Time Approximation Scheme for Euclidean Minimum Cost k-Connectivity

  1998cited by this paper
• Approximation schemes for Euclidean k-medians and related problems

  1998cited by this paper
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems

  1998cited by this paper
• Approximating geometrical graphs via “spanners” and “banyans”

  1998cited by this paper
• Probabilistic approximation of metric spaces and its algorithmic applications

  1996cited by this paper
• On the Complexity of Approximating Euclidean Traveling Salesman Tours and Minimum Spanning Trees

  1996cited by this paper
• A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields

  1995cited by this paper
• A randomized linear-time algorithm to find minimum spanning trees

  1995cited by this paper
• Approximating Euclidean distances by small degree graphs

  1994cited by this paper
• A fast algorithm for constructing sparse Euclidean spanners

  1994cited by this paper
• A sparse graph almost as good as the complete graph on points inK dimensions

  1991cited by this paper
• Constructing multidimensional spanner graphs

  1991cited by this paper
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths

  1990cited by this paper
• An effective way to represent quadtrees

  1982cited by this paper
• The traveling salesman problem

  1961cited by this paper
• Journal of Graph Algorithms and Applications Low-distortion Embeddings of Trees

  year unknowncited by this paper
• Max-planck-institut @bullet@bullet Fur Informatik Dynamie Algorithms for Geometrie Spanners of Small Diameter: Randomized Solutions Dynamie Algorithms for Geometrie Spanners of Small Diameter: Randomized Solutions Dynamic Algorithms for Geometrie Spanners of Small Diameter: Randomized Solutions*

  year unknowncited by this paper

• A (5/3+ε)-Approximation for Tricolored Non-crossing Euclidean TSP

  2024cites this paper
• A Linear Time Gap-ETH-Tight Approximation Scheme for Euclidean TSP

  2024cites this paper
• Highway Dimension: a Metric View

  2024cites this paper
• Novel Properties of Hierarchical Probabilistic Partitions and Their Algorithmic Applications

  2024cites this paper
• A Linear Time Gap-ETH-Tight Approximation Scheme for TSP in the Euclidean Plane

  2024influential citation
• Euclidean Capacitated Vehicle Routing in the Random Setting: A 1.55-Approximation Algorithm

  2024cites this paper
• Quasi-linear time heuristic to solve the Euclidean traveling salesman problem with low gap

  2024cites this paper
• New Approximation Algorithms for Fair k-median Problem

  2022cites this paper
• Near-Linear ε-Emulators for Planar Graphs

  2022cites this paper
• Near-Linear $\varepsilon$-Emulators for Planar Graphs

  2022cites this paper
• Almost-linear ε-emulators for planar graphs

  2022cites this paper
• 1 4 M ay 2 01 5 A light metric spanner

  2021cites this paper
• On the Approximability of the Traveling Salesman Problem with Line Neighborhoods

  2020cites this paper
• Polynomial Time Approximation Schemes for Clustering in Low Highway Dimension Graphs

  2020cites this paper
• On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs

  2020cites this paper
• A Gap-ETH-Tight Approximation Scheme for Euclidean TSP

  2020cites this paper
• Approximation Algorithms for Traveling Salesman Problems

  2020cites this paper
• Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces

  2019influential citation
• Near-Linear Time Approximations Schemes for Clustering in Doubling Metrics

  2019cites this paper
• An ETH-Tight Exact Algorithm for Euclidean TSP

  2018cites this paper
• A PTAS for Euclidean TSP with Hyperplane Neighborhoods

  2018cites this paper
• Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics

  2018influential citation
• Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time

  2017cites this paper
• 31 SHORTEST PATHS AND NETWORKS

  2017cites this paper
• Reducing Curse of Dimensionality

  2016influential citation
• Approximation Schemes for Geometric Network Optimization Problems

  2016cites this paper
• Euclidean Traveling Salesman Problem

  2016cites this paper
• Maximum Scatter TSP in Doubling Metrics

  2015cites this paper
• A Light Metric Spanner

  2015influential citation
• Approximating the Regular Graphic TSP in Near Linear Time

  2014cites this paper
• Socially inspired algorithms for the travelling thief problem

  2014influential citation
• Light spanners for Snowflake Metrics

  2014cites this paper
• Dimension reduction techniques for ℓp, 1 ≤ p < ∞, with applications

  2014cites this paper
• ec 2 01 5 Dimension reduction techniques for l p ( 1 ≤ p ≤ 2 ) , with applications

  year unknowncites this paper