Effective Tour Searching for TSP by Contraction of Pseudo Backbone Edges

1. Applegate, D.L., Bixby, R.E., Chvátal, V., Cook, W.J.: The Traveling Salesman Problem. A Computational Study. Princeton University Press, Princeton (2006)

   MATH  Google Scholar 

2. Applegate, D.L., Bixby, R.E., Chvátal, V., Cook, W.J., Espinoza, D., Goycoolea, M., Helsgaun, K.: Certification of an optimal Tour through 85,900 cities. Oper. Res. Lett. 37(1), 11–15 (2009)

   Article  MATH  MathSciNet  Google Scholar 

3. Cook, W., Seymour, P.: Tour Merging via Branch-Decomposition. INFORMS J. Comput. 15(3), 233–248 (2003)

   Article  MATH  MathSciNet  Google Scholar 

4. Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)

   Book  MATH  Google Scholar 

5. Ernst, C., Dong, C., Jäger, G., Molitor, P., Richter, D.: Finding Good Tours for Huge Euclidean TSP Instances by Iterative Backbone Contraction (submitted for Publication, 2009)

   Google Scholar 

6. Fischer, T., Merz, P.: Reducing the Size of Traveling Salesman Problem Instances by Fixing Edges. In: Cotta, C., van Hemert, J. (eds.) EvoCOP 2007. LNCS, vol. 4446, pp. 72–83. Springer, Heidelberg (2007)

   Chapter  Google Scholar 

7. Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)

   MATH  Google Scholar 

8. Goldengorin, B., Jäger, G., Molitor, P.: Some Basics on Tolerances. In: Cheng, S.-W., Poon, C.K. (eds.) AAIM 2006. LNCS, vol. 4041, pp. 194–206. Springer, Heidelberg (2006)

   Chapter  Google Scholar 

9. Goldengorin, B., Jäger, G., Molitor, P.: Tolerances Applied in Combinatorial Optimization. J. Comput. Sci. 2(9), 716–734 (2006)

   Article  Google Scholar 

10. Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. SIGACT News 38(1), 31–45 (2007)

    Article  Google Scholar 

11. Gutin, G., Punnen, A.P. (eds.): The Traveling Salesman Problem and Its Variations. Kluwer, Dordrecht (2002)

    MATH  Google Scholar 

12. Helsgaun, K.: An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic. European Journal Oper. Res. 126(1), 106–130 (2000)

    Article  MATH  MathSciNet  Google Scholar 

13. Helsgaun, K.: An Effective Implementation of K-opt Moves for the Lin-Kernighan TSP Heuristic. Writings on Computer Science 109 (2007)

    Google Scholar 

14. Hüffner, F.: Algorithms and Experiments for Parameterized Approaches to Hard Graph Problems. PhD Thesis, Friedrich-Schiller-University Jena, Germany (2007)

    Google Scholar 

15. Kilby, P., Slaney, J.K., Walsh, T.: The Backbone of the Travelling Salesperson. In: Kaelbling, L.P., Saffiotti, A. (eds.) Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI 2005), pp. 175–180 (2005)

    Google Scholar 

16. Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B. (eds.): The Traveling Salesman Problem - A Guided Tour of Combinatorial Optimization. John Wiley & Sons, Chicester (1985)

    MATH  Google Scholar 

17. Lin, S., Kernighan, B.W.: An Effective Heuristic Algorithm for the Traveling Salesman Problem. Oper. Res. 21, 498–516 (1973)

    Article  MATH  MathSciNet  Google Scholar 

18. Möbius, A., Freisleben, B., Merz, P., Schreiber, M.: Combinatorial Optimization by Iterative Partial Transcription. Phys. Rev. E 59(4), 4667–4674 (1999)

    Article  Google Scholar 

19. Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., Troyanski, L.: Determining Computational Complexity for Characteristic Phase Transitions. Nature 400, 133–137 (1998)

    MathSciNet  Google Scholar 

20. Niedermeier, R.: Invitation to Fixed-Parameter Tractability. Oxford University Press, Oxford (2006)

    Book  MATH  Google Scholar 

21. Reinelt, G.: TSPLIB – a Traveling Salesman Problem Library. ORSA J. Comput. 3, 376–384 (1991)

    Article  MATH  Google Scholar 

22. Ribeiro, C.C., Toso, R.F.: Experimental Analysis of Algorithms for Updating Minimum Spanning Trees on Graphs Subject to Changes on Edge Weights. In: Demetrescu, C. (ed.) WEA 2007. LNCS, vol. 4525, pp. 393–405. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

23. Richter, D.: Toleranzen in Helsgauns Lin-Kernighan-Heuristik für das TSP. Diploma Thesis, Martin-Luther-University Halle-Wittenberg, Germany (2006)

    Google Scholar 

24. Richter, D., Goldengorin, B., Jäger, G., Molitor, P.: Improving the Efficiency of Helsgaun’s Lin-Kernighan Heuristic for the Symmetric TSP. In: Janssen, J., Prałat, P. (eds.) CAAN 2007. LNCS, vol. 4852, pp. 99–111. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

25. Slaney, J.K., Walsh, T.: The Backbones in Optimization and Approximation. In: Nebel, B. (ed.) Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI 2001), pp. 254–259 (2001)

    Google Scholar 

26. Zhang, W., Looks, M.: A Novel Local Search Algorithm for the Traveling Salesman Problem that Exploits Backbones. In: Kaelbling, L.P., Saffiotti, A. (eds.) Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI 2005), pp. 343–350 (2005)

    Google Scholar 

27. DIMACS Implementation Challenge: http://www.research.att.com/~dsj/chtsp/

28. TSPLIB: http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html

29. TSP Homepage, http://www.tsp.gatech.edu/

30. National Instances from the TSP Homepage, http://www.tsp.gatech.edu/world/summary.html

31. VLSI Instances from the TSP Homepage, http://www.tsp.gatech.edu/vlsi/summary.html

32. World TSP from the TSP Homepage, http://www.tsp.gatech.edu/world/

33. Source Code of [1] (Concorde), http://www.tsp.gatech.edu/concorde/index.html

34. Source Code of [12] (LKH), http://www.akira.ruc.dk/~keld/research/LKH/

35. Additional Information about Experiments of this Paper, http://www.informatik.uni-halle.de/ti/forschung/toleranzen/kantenkontraktion

Download references