On the empirical time complexity of finding optimal solutions vs proving optimality for Euclidean TSP instances
Tóm tắt
Từ khóa
Tài liệu tham khảo
The traveling salesman problem. Version visited last on 15 April 2014. http://www.math.uwaterloo.ca/tsp/ (2014)
Applegate, D.: Personal communication (2009)
Applegate, D., Bixby, R.E., Chvatal, V., Cook, W.J.: The traveling salesman problem: a computational study. Princeton University Press, Princeton (2006)
Applegate, D., Bixby, R.E., Chvatal, V., Cook, W.J.: Concorde TSP solver. Version visited last on 15 April 2014. http://www.math.uwaterloo.ca/tsp/concorde.html (2014)
Beame, P., Pitassi, T.: Propositional proof complexity: past, present, and future. In: Current trends in theoretical computer science: entering the 21st century, pp. 42–70. World Scientific Publishing (2001)
Dash, S.: Exponential lower bounds on the lengths of some classes of branch-and-cut proofs. Math. Oper. Res. 30(3), 678–700 (2005)
Helsgaun, K.: An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126, 106–130 (2000)
Helsgaun, K.: General k-opt submoves for the Lin-Kernighan TSP heuristic. Math. Program. Comput. 1(2–3), 119–163 (2009)
Hoos, H.H., Stützle, T.: On the empirical scaling of run-time for finding optimal solutions to the traveling salesman problem. Eur. J. Oper. Res. 238(1), 87–94 (2014)
Lawler, E.L., Lenstra, J.K., Rinnooy Kan., A.H.G, Shmoys, D.B.: The traveling salesman problem. Wiley, Chichester (1985)
Nagata, Y., Kobayashi, S.: A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem. INFORMS J. Comput. 25(2), 346–363 (2013)
Pipatsrisawat, K., Darwiche, A.: On the power of clause-learning SAT solvers as resolution engines. Artif. Intell. 175, 512–525 (2011)
Reinelt, G.: The traveling salesman: computational solutions for TSP applications. Lecture Notes in Computer Science, vol. 840. Springer, Heidelberg, Germany (1994)
Reinelt, G.: TSPLIB. Version visited last on 15 June 2012, http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95 (2012)