1
$\begingroup$

It is known that metric TSP can be approximated within some constant value, such as 3/2 through Christofides' algorithm. It is also known that non-metric TSP cannot be approximated within some constant value (unless P= NP), thanks to Sahni and Gonzalez.

It isn't clear however if non-metric TSP can be approximated within some non-constant value, such as the number of nodes of the instance, or the largest cost on its edges? Does Sahni and Gonzalez's result still hold for these values?

$\endgroup$
2
$\begingroup$

Indeed, it trivially can. If each edge has positive integer weight $w_e$, then any algorithm that outputs a valid tour has approximation ratio $w_{max} = \max_e w_e$, since the optimal solution costs at least $n \cdot 1 = n$ while the cost of any valid tour $T$ is at most $\sum_{e \in T} w_e \le n \cdot w_{max}$.

Note: If edges can have weight zero this argument won't work, because in that case even deciding if a tour of cost zero exists is NP-hard; you can reduce Hamiltonian Cycle to it. Hence your algorithm will sometime output a nonzero cost tour, when a zero cost tour exists, which means the approximation ratio cannot be bounded.

$\endgroup$
0
$\begingroup$

TSP can be used to solve “Hamiltonian path”: is there a path connecting all nodes?

You do this by specifying a TSP instance where distance = 1 if two nodes are connected, distance = H otherwise (where H is some huge number), and checking if the shortest path has length n (instead of n + H - 1)

An approximation cannot be good enough to solve Hamiltonian path.

I have never seen this mentioned, but I could imagine that "almost Hamiltonian path" where you are supposed to find a sequence of n nodes of which at least n-m are connected would be NP-complete for some combinations of n and m, for example if m=1. In that case, an approximation better than m * H would solve the "almost Hamiltonian path" problem.

You can find a path by starting at some node and then always going to the nearest neighbour. You can take that as a baseline, or n times the longest distance, or the sum of the longest distances from each node. I suspect you won't be better than this baseline times some small constant.

On the other hand, you can turn a TSP into TSP with metric by increasing all distances by some value. You can determine the minimum increase to guarantee triangular equation, and go from there.

$\endgroup$
  • $\begingroup$ This is the proof that non-metric TSP cannot be approximated within some non-constant value. It doesn't seem to prove that an approximation algorithm of ratio "huge" cannot exist. $\endgroup$ – J. Schmidt Sep 24 at 15:12
  • $\begingroup$ Well, no approximation better than the difference between largest and smallest distance. I could imagine that "almost Hamiltonian path" (with one or two or a few missing connections) would still be NP complete. $\endgroup$ – gnasher729 Sep 26 at 7:17
  • $\begingroup$ I am pretty sure that finding a "long" path is NP hard. With long I mean any path length that depends on n. This could be shown by reducing Hamilton path to this f(n) path problem by adding indepent sets of appropriate size. $\endgroup$ – Daniel Sep 26 at 7:55
  • $\begingroup$ "On the other hand, you can turn a TSP into TSP with metric by increasing all distances by some value. You can determine the minimum increase to guarantee triangular equation, and go from there." Using an approximation algorithm on the resulting metric tsp instance, doesn't guarantee an approximated solution for the initial non-metric instance though. $\endgroup$ – J. Schmidt Sep 26 at 12:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.