1
$\begingroup$

Is there a known (polynomial in number of nodes) algorithm to generate TSP instances with known optimal value?

The idea is to be able to generating arbitrary large instances with known optimal value, in order to be able to test heuristics on them.

I found the paper Arthur, J. & Frendeway, J. Generating Travelling-Salesman Problems with Known Optimal Tours, The Journal of the Operational Research Society, Vol. 39, No. 2 (Feb., 1988), pp. 153-159 for generating TSP with known optimal, alas I cannot access it.

Improve this question
$\endgroup$
12
  • 2
    $\begingroup$ Yes; put the vertices of the graph in a cycle. Or, easier, create a graph which has no Hamilton path (i.e. with multiple components). I assume you want to exclude such simple counterexamples but you'll have to specify how. $\endgroup$ – SamM Apr 25 '13 at 21:24
  • 1
    $\begingroup$ Or the vertices on a single line. $\:$ $\endgroup$ – user6973 Apr 25 '13 at 21:44
  • 4
    $\begingroup$ Why do you need a polynomial-time algorithm? Any instances that can be solved by hand in a few minutes can also solve with a computer in a fraction of a second, using the same algorithm you're asking your students to use (presumably brute force). Or are you looking for instances with some special structure (for example: no near-optimal tours)? $\endgroup$ – Jeffε Apr 26 '13 at 13:56
  • 1
    $\begingroup$ Could you please update the original question? Since the problem is trivial otherwise, the question should require that the nearest/farthest neighbor heuristic gives the wrong answer. Also: polynomial in what? What's the input? $\endgroup$ – Jeffε Apr 27 '13 at 16:56
  • 1
    $\begingroup$ ps: I still not convinced this question is suitable for cstheory, you may want to read this. The paper you wrote you have found is the same as the paper in your previous question from last year, not sure why keep linking to it. Also I don't see why the answer given to your previous question does not work for this new one. $\endgroup$ – Kaveh Apr 28 '13 at 6:35

Your Answer

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

Browse other questions tagged or ask your own question.