3
$\begingroup$

This question is motivated by my impression, that finding better heuristics for the TSP problem (or any other $NP$-complete problem) is "only" of practical interest, but doesn't provide any progress towards a decision of the $P=NP$ question.

The reason for my impression is that all heuristics I'm aware of, do not have the same "invariants" that optimal tours have, most prominently the invariance of the solution set of edges if the problem instance is subjected to the addition of vertex weights.

The Christofides heuristic for example had the best theoretical upper length-bounds for the tours it generates for at least two decades and still is better than the best tour expansion heuristics, IMHO there is nothing that can be concluded from that difference in performance, that would help to understand, why $NP$ problems are so hard.


Question:

is my impression right or are there examples of heuristics that are considered to have contributed to progress in answering the $NP=P$ question, because they are based on newly discovered provable properties of optimal tours?


I am looking for theorems about the $NP=P$ problem that made, resp. make, use of (then) novel ideas of TSP heristics or, were motivated by such ideas. I kindly would ask to abstain from expressing opinions about subject; the importance of research on better heuristics is unquestionable to me!

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
4
$\begingroup$

Yes. From J. M. Steele's "Probability theory and Combinatorial Optimization", page 40,

In particular, Karp (1976) observed that under a variety of natural probability models, one can build fast algorithms that will yield nearly optimal solutions with probability one. This discovery was especially engaging in the case of the TSP, where Papadimitriou (1978a) had proved that even in the case of the Euclidean plane, the problem of determining a shortest path is NP-complete. Thus Karp's partitioning algorithm gave the first examples of an NP-complete problem for which there exists a polynomial-time algorithm such that with probability one the algorithm provides a solution that is within a factor of $1+\epsilon$ times the value of the optimal solution.

The heuristic in question is Karp's partitioning scheme: http://www-math.mit.edu/~goemans/18.415-1996/karp.ps

Improve this answer
$\endgroup$
3
  • $\begingroup$ there is a glitch in your answer: it is not the shortest path, but the shortest Hamilton cycle in the Euclidean plane, whose determination has been proved NP complete $\endgroup$
    – Manfred Weis
    Commented Dec 20, 2017 at 6:13
  • $\begingroup$ I'm just writing what was in Steele's book. But the distinction between the cycle and the path becomes unimportant because the result concerns limiting behavior as $n\to\infty$ in the unit square, and the two can only differ by a constant term of at most $\sqrt{2}$. Thus, the important point -- the last sentence -- is exactly correct as written. $\endgroup$
    – John Gunnar Carlsson
    Commented Dec 20, 2017 at 22:29
  • 1
    $\begingroup$ There is of course no essential difference between the shorthest Hamilton cycle problem and the shortest Hamilton path problem, but the word "Hamilton" is missing in your answer and thus could be misread as the ordinary shortest path problem between two of a finite set of points in the Euclidean plane. My suggestion would therefore be to reformulate to "...even in the case of the Euclidean plane, the problem of determining a shortest Hamilton path is NP-complete" $\endgroup$
    – Manfred Weis
    Commented Dec 21, 2017 at 6:35
3
$\begingroup$

I'm not sure if this is exactly the kind of thing you are looking for but I think it is close.

Around 1986, E. R. Swart at the University of Guelph wrote a technical report entitled "P = NP" that claimed to have proved that P = NP by formulating the TSP as a linear program (note: not an integer linear program but an ordinary linear program with no integrality condition imposed by fiat) of polynomial size.

Of course, the paper had a fatal error, but it prompted Mihalis Yannakakis to prove that there is no subexponential size linear program for the TSP that is symmetric (meaning that it is invariant under any permutation of the cities): Expressing combinatorial optimization problems by linear programs, J. Comput. Sys. Sci. 43 (1991), 441–466. This result was later improved by Thomas Rothvoß, Some 0/1 polytopes need exponential size extended formulations, Math. Program. Ser. A 142 (2013), 255–268, who eliminated the need for the hypothesis that the linear program be symmetric.

The theorem of Yannakakis and Rothvoß is considered to be an important theoretical step towards understanding the P = NP problem. Swart's proposed linear programming formulation was not exactly a "heuristic," but it was at least a proposed algorithm, and it did indirectly contribute to the theoretical advance.

Improve this answer
$\endgroup$
1
  • $\begingroup$ your answer fits my bill. $\endgroup$
    – Manfred Weis
    Commented Dec 20, 2017 at 6:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .