Domination analysis of some heuristics for the traveling salesman problem

DOI10.1016/S0166-218X(01)00268-2zbMath1041.90063MaRDI QIDQ1602706

Santosh N. Kabadi, Abraham P. Punnen

Publication date: 24 June 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP ⋮ When the greedy algorithm fails ⋮ Domination analysis for minimum multiprocessor scheduling ⋮ The bilinear assignment problem: complexity and polynomially solvable special cases ⋮ Transformations of generalized ATSP into ATSP. ⋮ Cyclic transfers in school timetabling ⋮ Domination analysis of combinatorial optimization problems. ⋮ Upper bounds on ATSP neighborhood size. ⋮ Analysis of 2-Opt Heuristic for the Winner Determination Problem Under the Chamberlin-Courant System ⋮ Average value of solutions of the bipartite quadratic assignment problem and linkages to domination analysis ⋮ Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms ⋮ Dominance guarantees for above-average solutions ⋮ A survey of very large-scale neighborhood search techniques ⋮ Extended neighborhood: Definition and characterization ⋮ TSP tour domination and Hamilton cycle decompositions of regular digraphs ⋮ Worst case analysis of max-regret, greedy and other heuristics for multidimensional assignment and traveling salesman problems ⋮ Anti-matroids

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficiency of a local algorithm for solving the traveling salesman problem
• Local search and the local structure of NP-complete problems
• Exponential neighbourhood local search for the traveling salesman problem
• Gilmore-Gomory type traveling salesman problems
• Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number
• Ejection chains, reference structures and alternating path methods for traveling salesman problems
• The Travelling Salesman and the PQ-Tree
• The traveling salesman problem: new polynomial approximation algorithms and domination analysis
• P-Complete Approximation Problems
• The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms
• Implementation of a linear time algorithm for certain generalized traveling salesman problems
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem