53
I've studied the problem and I found the best known algorithms for TSP.
$n$ is the number of vertices, $M$ is the maximal edge weight.
All bounds are given up to a polynomial factor of the input size ($poly(n, \log M)$).
We denote Asymmetric TSP by ATSP.
1. Exact Algorithms for TSP
1.1. General ATSP
$M2^{n-\Omega(\sqrt{n/\log (Mn)})}$ time and $exp$-...
27
A 1.1-approximation can be obtained in time (and space) $O^*(1.932^n)$ by adapting a "truncated" version of Held and Karp's exact $O^*(2^n)$ algorithm. Here $n$ is the number of locations. More in general, a $(1+\epsilon)$-approximation can be found in time $O^*(2^{(1-\epsilon/2)n})$ for all $\epsilon \le 2/5$. This is from:
Nicolas Boria, Nicolas Bougeois,...
21
Here is a simple reduction for the TSP problem to the metric TSP problem:
For the given TSP instance with $n$ cities, let $D(i,j) \geq 0$ denote the distance between $i$ and $j$. Now let $M = \max_{i,j} D(i,j)$. Define the metric TSP instance by the distances $D'(i,j) := D(i,j)+M$. To see that this gives a metric TSP instance, let $i,j,k$ be arbitrary. Then ...
answered Oct 22 '12 at 15:02
Kristoffer Arnsfelt Hansen
3,9052 gold badges22 silver badges34 bronze badges
21
This is a special case of the Travelling Salesman with Neighborhoods (TSPN) problem. In the general version, the neighborhoods need not all be the same.
A paper by Dumitrescu and Mitchell, Approximation algorithms for TSP with neighborhoods in the plane, addresses your question. They give a constant factor approximation algorithm for a slightly more general ...
19
Q1. This is a notorious open problem. It is known to be in the fourth level of the counting hierarchy, due to [ABKM]. Not known to be in NP. The problem is not really in computing square roots as claimed in the lecture notes: $n$ bits of a square root of an integer can be computed in time polynomial in $n$ and the bitsize of the integer. The problem is, ...
15
The problem of finding the shortest tour that covers a given number k of nodes is usually referred to as k-TSP. Searching Google scholar for that term will find some relevant literature. It is NP-hard but can be approximated within a constant factor. So finding an exact solution may be out of reach, unless you're prepared to use sophisticated branch and ...
14
No, the NN heuristic does not have constant factor for metric TSP.
Rosenkrantz, Stearns, and Lewis proved in An Analysis of Several Heuristics for the Traveling Salesman Problem. SIAM J. Comput. 6(3): 563-581 (1977) that the worst case ratio of the tour obtained by the nearest neighbor method is bounded above by a logarithmic function of the number of ...
12
I hope this partly answers your question: Most known heuristics like Greedy, Naerest Neighbor, Lin-Kerninhan etc.
perfrom quite well for (symmetric) TSP without triangle inequality.
You may check these heuristics with the Concorde TSP Solver
which is the best TSP solver I know so far.
In theory, there is no heuristic for TSP without triangle inequality ...
10
EDIT (UPDATE): The lower bound in my answer below was proven (by a different proof) in "On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees", by Das et al; Algorithmica 19:447-460 (1997).
is it possible to achieve even an approximation ratio like $O(n^{1-\epsilon})$ for some $\epsilon>0$ in $o(n\log n)$ time ...
10
As far as I know, dynamic programming does the trick
Klein's paper on TSP for planar graphs has the details for planar graphs with bounded tree-width.
If the graph is not planar, the dynamic program is slower (dependency on the tree-width is worse).
Philip N. Klein: A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights. ...
10
A similar question can be asked for any problem where we have a lower bound $\alpha$ on the approximability and an upper bound $\beta$ and currently $\alpha < \beta$. I am assuming that the questioner is interested in sub-exponential time algorithms. This depends on the unknown "truth". Say the problem is NP-Hard to approximate to within a factor $\gamma$ ...
10
There is no way to choose the parameters A, B, C, D properly;
as it is the case for most heuristics, the parameters are chosen ''by experience''.
Worse, there is no guarantee that the solution (the array of the outputs)
of this heuristic is indeed a feasible TSP tour!
In this context, perhaps interesting to read: Wilson and Pawley,
On the stability of ...
10
One relevant TSP version is "Group TSP". In this problem, the "cities" are divided into groups and the goal is to find a tour that visits each group at least once.
This has also been studied on the plane, which is closer to what you describe. Here each group is a closed region of the plane and it suffices to visit one point in the region to cover it. See e....
8
I think the following example with four points answers your question (though it gives multi-sets of distances). See Reconstructing Sets From Interpoint Distances by Skiena, Smith, and Lemke for more information.
8
I've studied the problem and I found some results.
Shortest Common Superstring (SCS) can be solved in time $2^n$ with only polynomial space(Kohn, Gottlieb, Kohn; Karp; Bax, Franklin).
The best known approximation is $2\frac{11}{30}$ (Paluch).
The best known approximation of compression is $3\over4$ (Paluch).
If SCS can be approximated by a factor $\alpha$ ...
6
One general approach to generating harder instances is as follows:
Start with a random problem instance.
Embed a "hidden backdoor": randomly choose a good solution (one that's likely to be much better than any solution that already exists) and modify the problem instance to forcibly embed this solution into the problem instance.
For instance, for TSP, you ...
5
Here's the shortest superstring problem: you are given $n$ strings $s_1,\ldots, s_n$ over some alphabet $\Sigma$ and you want to find the shortest string over $\Sigma$ that contains each $s_i$ as a subsequence of consecutive characters, i.e. a substring.
When we talk about exact algorithms for the problem, finding the length $L$ of the shortest superstring ...
5
Assuming the strings have length polynomial in $n$, then yes, there is at least a $2^{n-\Omega(\sqrt{n/\log n})}$ time solution. The reason is the well-known reduction from the shortest common superstring problem to ATSP with polynomial sized integer weights, which you in turn can solve by polynomial interpolation if you can count Hamiltonian cycles in a ...
4
Take a look at Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan van Rooij, Jakub Onufry Wojtaszczyk, "Solving connectivity problems parameterized by treewidth in single exponential time", 2011.
I think you can use their ideas to get a randomized $\mbox{poly}(n)2^{O(k)}$ time algorithm for treewidth-$k$ graphs on $n$ vertices.
4
I believe for treewidth-$k$ graphs, the problem is exactly solvable in time polynomial in $n$ and $k^k$. This is true also for the metric problem on weighted bounded treewidth graphs. One does a dynamic program, where for each bag, you have an entry for every possible way of crossing from one side of the bag to the other. With $k$ nodes in the bag, one has ...
4
The Vehicle Routing Problem was introduced in G. B. Dantzig and J. H. Ramser, The Truck Dispatching Problem, Management Science Vol. 6, No. 1 (Oct., 1959), pp. 80-91.
The authors underline the differences with TSP in this way:
... The "truck dispatching problem" formulated in this paper may be considered as a generalization of the TSP ...
... The salesman ...
4
This is a special case of the precedence-constrained TSP which has been studied quite a lot. For instance, there are a polyhedral analysis by Balas, Fischetti and Pulleyblank, and a branch-and-cut algorithm by Ascheuer, Jünger and Reinelt.
3
You wrote:
On the other hand there is this paper by Papadimitriou: http://www.sciencedirect.com/science/article/pii/0304397577900123 saying it is NP-complete, which also means it is in NP. Although he doesn't prove it in the paper, I think he consider the membership in NP trivial, as is usually the case with such problems.
Why don't you simply read the ...
3
There is no algorithm that runs in time $o(n^2)$ on an $n$-point metric space and returns a tour with weight within a constant factor of the minimum weight: see the argument in Section 9 of this paper by Indyk.
On the other hand, if you just want an approximation to the weight of the optimal tour, without actually getting a tour, then you can use this ...
3
You can also transform the ATSP to TSP; the process requires doubling number of nodes (adding dummy cities).
http://www.sciencedirect.com/science/article/pii/0167637783900482
http://www.sciencedirect.com/science/article/pii/0167637786900817
3
an approach that often gives you high control over the nature of solutions is conversion from one NP complete problem to another. now you define "interesting" in your question in a statistical way, but another neat approach is to use classic problems from the field. my favorite is factoring/SAT. it is trivial to find either "smooth" numbers with lots of ...
2
In the year 1959, Dantzig and Ramser, the authos of "The truck dispatching problem" described how the Vehicle Routing Problem (VRP) may be considered as a generalization of the Travelling Salesman Problem (TSP). They described the generalization of the TSP with multiple salespeople (supposedly riding a single vehicle each), and called this the “Clover ...
2
This problem is PSPACE-complete even in the case in which the edge weights obey the triangle inequality. See
Hsi-Ming Ho, Joel Ouaknine, The Cyclic-Routing UAV Problem is PSPACE-Complete, FoSSaCS 2015
2
Each of the papers shows that there is a polynomial-time approximation scheme (PTAS) for the problem it studies if the input instance is Euclidean and that there is no PTAS if the input instance is arbitrary (if P≠NP).
1
Best one I know is the polytime approximation algorithm of Asadpour et al., although maybe this isn't what you want (i.e. you want exact solution, I'm guessing). Anyway, the algorithm achieves $O(\log n / \log \log n)$ approximation for $n$-vertex graphs.
Only top voted, non community-wiki answers of a minimum length are eligible
