Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems

By Sanjeev Arora. 1998

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Challenges and opportunities in quantum optimization (2023, unknown): “If the problem is restricted to the Euclidean TSP (in which all points are in the d -dimensional space d R and edge weights equal their Euclidean distances), then, remarkably, there exists an explicit PTAS to solve such TSP instances 31 .”
Protein design is NP-hard. (2002, background): “However, when restricted to the important subclass of Euclidean constant-dimension problems, finding exact optimal solutions remains NP-complete, but approximate TSP is dramatically easier (nearly linear-time for randomized algorithms) (Arora, 1998).”
An Energy-Efficient Mobile-Sink Path Selection Strategy for Wireless Sensor Networks (2014, background): “This is essentially the well-known traveling salesman problem (TSP) [30], where the goal is to find the shortest tour that visits all sensor nodes.”
Traveling Salesman Problem: an Overview of Applications, Formulations, and Solution Approaches (2010, background): “So far, the best known approximate algorithm available is due to (Arora, 1998).”
An improved LP-based approximation for steiner tree (2010, methodology): “In particular, a PTAS can be obtained by the technique of Arora [4] if the nodes are points in a fixed-dimension Euclidean space, and using the algorithm of Borradaile, Kenyon-Mathieu and Klein [7] for planar graphs.”
Improved Approximation Algorithms for the Uncapacitated Facility Location Problem (2003, methodology): “Their method is similar to the one used by Arora [Aro98] to produce approximation schemes for the traveling salesman problem.”
Rendezvous design algorithms for wireless sensor networks with a mobile base station (2008, background): “The algorithm in [1] has an approximation ratio of (1+1/b) and a complexity of O(|S|(log |S|)O(b)) for any fixedb > 1.”
A survey on algorithmic approaches for solving tourist trip design problems (2014, methodology): “In order to create the PTAS, an approximation algorithm is presented for the k − TSP in R d based on Mitchell’s approximation algorithm for the k − TSP Mitchell (1999) and Arora’s work on the same problem Arora (1998).”
Parameterized Complexity and Approximation Algorithms (2008, background): “However, in the journal version of the paper [7], the running-time of the algorithm is improved to |x| · log ) |x| = 2 (2)) · |x|2, hence the problem admits an EPTAS.”
Traveling Salesman Problems with Profits (2005, background): “of investigation has seen a huge development in the past few years, and several other papers have recently improved the approximation ratio for the k-MST problem, and consequently for the PCTSP (see Blum et al. 1999; Arora and Karakostas 2000; Arora 1998 ).”
The Design of Approximation Algorithms (2011, methodology): “Approximation schemes for Euclidean instances of the traveling salesman problem and some other geometric problems were discovered independently by Arora [11] and Mitchell [225].”
The status of the P versus NP problem (2009, background): “This problem remains NP-complete but Arora4 gives an efficient algorithm that gets very close to the best possible route.”
Diffusion models as plug-and-play priors (2022, background): “Although the general form of the TSP is NP-hard, a polynomial-time approximation scheme is known to exist in the Euclidean case [2, 26] and can yield proofs of tour optimality for small problems.”