Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn Empirical Analysis of Approximation Algorithms for the Euclidean Traveling Salesman Problem
203
0
0.0
(
0
)
Added by
Yihui He
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
With applications to many disciplines, the traveling salesman problem (TSP) is a classical computer science optimization problem with applications to industrial engineering, theoretical computer science, bioinformatics, and several other disciplines. In recent years, there have been a plethora of novel approaches for approximate solutions ranging from simplistic greedy to cooperative distributed algorithms derived from artificial intelligence. In this paper, we perform an evaluation and analysis of cornerstone algorithms for the Euclidean TSP. We evaluate greedy, 2-opt, and genetic algorithms. We use several datasets as input for the algorithms including a small dataset, a mediumsized dataset representing cities in the United States, and a synthetic dataset consisting of 200 cities to test algorithm scalability. We discover that the greedy and 2-opt algorithms efficiently calculate solutions for smaller datasets. Genetic algorithm has the best performance for optimality for medium to large datasets, but generally have longer runtime. Our implementations is public available.
rate research
Read More
We present the first nontrivial approximation algorithm for the bottleneck asymmetric traveling salesman problem. Given an asymmetric metric cost between n vertices, the problem is to find a Hamiltonian cycle that minimizes its bottleneck (or maximum-length edge) cost. We achieve an O(log n / log log n) approximation performance guarantee by giving a novel algorithmic technique to shortcut Eulerian circuits while bounding the lengths of the shortcuts needed. This allows us to build on a related result of Asadpour, Goemans, Mk{a}dry, Oveis Gharan, and Saberi to obtain this guarantee. Furthermore, we show how our technique yields stronger approximation bounds in some cases, such as the bounded orientable genus case studied by Oveis Gharan and Saberi. We also explore the possibility of further improvement upon our main result through a comparison to the symmetric counterpart of the problem.
A new characterisation of Hamiltonian graphs using f-cutset matrix is proposed. A new exact polynomial time algorithm for the travelling salesman problem (TSP) based on this new characterisation is developed. We then define so called ordered weighted adjacency list for given weighted complete graph and proceed to the main result of the paper, namely, the exact algorithm based on utilisation of ordered weighted adjacency list and the simple properties that any path or circuit must satisfy. This algorithm performs checking of sub-lists, containing (p-1) entries (edge pairs) for paths and p entries (edge pairs) for circuits, chosen from ordered adjacency list in a well defined sequence to determine exactly the shortest Hamiltonian path and shortest Hamiltonian circuit in a weighted complete graph of p vertices. The procedure has intrinsic advantage of landing on the desired solution in quickest possible time and even in worst case in polynomial time. A new characterisation of shortest Hamiltonian tour for a weighted complete graph satisfying triangle inequality (i.e. for tours passing through every city on a realistic map of cities where cities can be taken as points on a Euclidean plane) is also proposed. Finally, we propose a classical algorithm for unstructured search and also three new quantum algorithms for unstructured search which exponentially speed up the searching ability in the unstructured database and discuss its effect on the NP-Complete problems.
One of the most fundamental results in combinatorial optimization is the polynomial-time 3/2-approximation algorithm for the metric traveling salesman problem. It was presented by Christofides in 1976 and is well known as the Christofides algorithm. Recently, some authors started calling it Christofides-Serdyukov algorithm, pointing out that it was published independently in the USSR in 1978. We provide some historic background on Serdyukovs findings and a translation of his article from Russian into English.
Theory of computer calculations strongly depends on the nature of elements the computer is made of. Quantum interference allows to formulate the Shor factorization algorithm turned out to be more effective than any one written for classical computers. Similarly, quantum wave packet reduction allows to devise the Grover search algorithm which outperforms any classical one. In the present paper we argue that the quantum incoherent tunneling can be used for elaboration of new algorithms able to solve some NP-hard problems, such as the Traveling Salesman Problem, considered to be intractable in the classical theory of computer computations.
Recent papers on approximation algorithms for the traveling salesman problem (TSP) have given a new variant on the well-known Christofides algorithm for the TSP, called the Best-of-Many Christofides algorithm. The algorithm involves sampling a spanning tree from the solution the standard LP relaxation of the TSP, subject to the condition that each edge is sampled with probability at most its value in the LP relaxation. One then runs Christofides algorithm on the tree by computing a minimum-cost matching on the odd-degree vertices in the tree, and shortcutting the resulting Eulerian graph to a tour. In this paper we perform an experimental evaluation of the Best-of-Many Christofides algorithm to see if there are empirical reasons to believe its performance is better than that of Christofides algorithm. Furthermore, several different sampling schemes have been proposed; we implement several different schemes to determine which ones might be the most promising for obtaining improved performance guarantees over that of Christofides algorithm. In our experiments, all of the implemented methods perform significantly better than the Christofides algorithm; an algorithm that samples from a maximum entropy distribution over spanning trees seems to be particularly good, though there are others that perform almost as well.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
