Martin-Luther-Universität Halle-Wittenberg

Pseudo-Backbonekanten der TSP-Benchmark-Instanz nrw1379


Login für Redakteure



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

Computational Combinatorial Optimization, S. 261-304, 2001

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

S. Climer und 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), S. 707–712, IAAI Press, 2002.

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

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

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

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

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

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

G. Gutin, A. Yeo und 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, S. 81-86, 2002.

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

M. Held und R. Karp. The Traveling-Salesman Problem and Minimum Spanning Trees: Part II.
Math. Program. 1, S. 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, S. 106-130, 2000.

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

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

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

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

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

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

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

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

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

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

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

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

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


  • 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.

Zum Seitenanfang