Skip to main content

New answers tagged

2 votes
Accepted

Hardness of the Metric TSP for the Maximum Metric

It is NP-hard, here's a proof. In [1], it is shown that the Hamiltonian path problem is NP-hard on induced subgraphs of the infinite grid (i.e. graphs that are defined by taking a set of integer ...
Laakeri's user avatar
  • 1,821

Top 50 recent answers are included