Martin Luther University Halle-Wittenberg

Pseudo-Backbonekanten der TSP-Benchmark-Instanz nrw1379

Further settings

Login for editors

Literatur

Literature

David Applegate, Robert E. Bixby, Vasek Chvtal, and William Cook. TSP Cuts Which Do Not Conform to the Template Paradigm.
donet.pdf    (externe Datei)

Computational Combinatorial Optimization, p. 261-304, 2001

G. Carpaneto, M. Dell’Amico, and P. Toth. Exact Solution of Large-Scale, Asymmetric Traveling Salesman Problems.
ACM Trans. Math. Software 21(4), p. 394-409, 1995.

S. Climer, and W. Zhang. Searching for Backbones and Fat: A Limit- Crossing Approach with Applications.
paper02.pdf    (externe Datei)

In: 18th National Conference on Artificial Intelligence (AAAI) and 14th Conference on Innovative Applications of Artificial Intelligence (IAAI), p. 707–712, IAAI Press, 2002.

S. Climer, and W. Zhang. Cut-and-Solve: An Iterative Search Strategy for Combinatorial Optimization Problems.
paper07.pdf    (externe Datei)

Artificial Intelligence 170, p. 714-738, 2006.

D. Gamboa, C. Rego, and F. Glover. Implementation Analysis of Efficient Heuristic Algorithms for the Traveling Salesman Problem.
COR_IAEH_TSP.pdf    (externe Datei)

Comput. Oper. Res. 33(4), p. 1154–1172, 2006.

F. Glover, G. Gutin, A. Yeo, and A. Zverovich. Construction Heuristics for the Asymmetric TSP.
constr2.ps    (externe Datei)

European J. Oper. Res. 129, p. 555-568, 2001.

G. Gutin, A. Yeo, and A. Zverovich. Traveling Salesman Should not be Greedy: Domination Analysis of Greedy Type Heuristics for the TSP.
BRICS-RS-01-6.pdf    (externe Datei)

Discrete Appl. Math. 117, p. 81-86, 2002.

M. Held and R. Karp. The Traveling-Salesman Problem and Minimum Spanning Trees.
Oper. Res. 18., p. 1138–1162, 1970.

M. Held and R. Karp. The Traveling-Salesman Problem and Minimum Spanning Trees: Part II.
Math. Program. 1, p. 16–25, 1971.

K. Helsgaun. An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic.
LKH_REPORT.pdf    (externe Datei)

European J. Oper. Res. 126, p. 106-130, 2000.

D.S. Johnson and L.A. McGeoch. The Traveling Salesman Problem: A Case Study in Local Optimization.
In: E.H.L. Aarts and J.K. Lenstra, Local Search in Combinatorial Optimization, p. 215-310, 1997.

R. Jonker and A. Volgenant. A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems.
Computing 38(4), p. 325-340, 1987.

R.M. Karp. A Patching Algorithm for the Non-Symmetric Traveling Salesman Problem.
SIAM J. Comput. 8, p. 561-573, 1979.

M. Libura. Sensitivity Analysis for Minimum Hamiltonian Path and Traveling Salesman Problems.
Discrete Appl. Math. 30, p. 197-211, 1991.

S. Lin and B.W. Kernighan. An Effective Heuristic Algorithm for the Traveling-Salesman Problem.
Oper. Res. 21, p. 498-516, 1973.

D.L. Miller and J.F. Pekny. Exact Solution of Large Asymmetric Traveling Salesman Problems.
Science 251, p. 754-761, 1991.

G. Reinelt. TSPLIB - a Traveling Salesman Problem Library.
ORSA J. Comput. 3, p. 376-384, 1991.

A. Volgenant. An Addendum on Sensitivity Analysis of the Optimal Assignment.
European J. Oper. Res. 169, p. 338-339, 2006.

W. Zhang. Truncated Branch-and-Bound: A Case Study on the Asymmetric TSP.
atsp-aaai93-symp.ps    (externe Datei)

In: AAAI Spring Symposium on AI and NP-Hard Problems, p. 160-166, 1993.

W. Zhang. Configuration Landscape Analysis and Backbone Guided Local Search: Part I: Satisfiability and Maximum Satisfiability.
Artificial Intelligence 158(1), p. 1-26, 2004.

W. Zhang and M. Looks. A Novel Local Search Algorithm for the Traveling Salesman Problem that Exploits Backbones.
1443.pdf    (externe Datei)

In: L.P. Kaelbling and A. Saffiotti, 19th International Joint Conference on Artificial Intelligence (IJCAI), p. 343-350, Professional Book Center, 2005.

Books

  • G. Gutin. A.P. Punnen, The Traveling Salesman Problem and Its Variations.
    Series: Combinatorial Optimization, Vol. 12, 2002. ISBN: 1-4020-0664-0
  • Lawler, Lenstra, Rinnooy Kan, Shmoys (Hrsg.). The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization.
    Wiley, 1985. ISBN: 0-471-90413-9
  • N. Christofides. Graph Theory - an Algorithmic Approach.
    Academic Press, New York, 1975.

Up