The Stack Overflow podcast is back! Listen to an interview with our new CEO.

New answers tagged

2

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 ...


0

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 ...


Top 50 recent answers are included