patternMinor
Can non-metric TSP be approximated within some non-constant value?
Viewed 0 times
tspcanapproximatedconstantnonvaluewithinmetricsome
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#115077, answer score: 3
Revisions (0)
No revisions yet.