TSP heuristics: domination analysis and complexity

DOI10.1007/S00453-002-0986-1MaRDI QIDQ1566378zbMATH OpenOpenAlexFDO

Authors Abraham P. Punnen, François Margot, Santosh N. Kabadi

Publication date 2 June 2003

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-002-0986-1

zbMATH Keywords

Computational complexityApproximation algorithmsTraveling salesman problemDomination analysis

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Domination analysis of some heuristics for the traveling salesman problem
• The traveling salesman problem: new polynomial approximation algorithms and domination analysis
• scientific article; zbMATH DE number 5886655
• Note on upper bounds for TSP domination number
• TSP tour domination and Hamilton cycle decompositions of regular digraphs

Cited in

(29)

• Fine-grained Complexity Analysis of Two Classic TSP Variants
• Symmetric weight constrained traveling salesman problem: Local search
• Minimum number of below average triangles in a weighted complete graph
• The bipartite QUBO
• Note on upper bounds for TSP domination number
• Greedy-type resistance of combinatorial problems
• Novel concave hull-based heuristic algorithm for TSP
• Anti-matroids
• Global strategies for augmenting the efficiency of TSP heuristics
• Domination analysis of some heuristics for the traveling salesman problem
• Fast heuristics and approximation algorithms
• The parallel complexity of TSP heuristics
• A domination algorithm for \(\{0,1\}\)-instances of the travelling salesman problem
• Worst case analysis of max-regret, greedy and other heuristics for multidimensional assignment and traveling salesman problems
• Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms
• Transformations of generalized ATSP into ATSP.
• When the greedy algorithm fails
• scientific article; zbMATH DE number 5855014 (Why is no real title available?)
• Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP
• The bilinear assignment problem: complexity and polynomially solvable special cases
• Average value of solutions of the bipartite quadratic assignment problem and linkages to domination analysis
• scientific article; zbMATH DE number 5886655 (Why is no real title available?)
• Domination analysis for minimum multiprocessor scheduling
• Fat computational complexity and heuristic design for the TSP
• Extended neighborhood: Definition and characterization
• Domination analysis of combinatorial optimization problems.
• Domination analysis of greedy heuristics for the frequency assignment problem.
• Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number
• Approximation algorithms with constant ratio for general cluster routing problems

This page was built for publication: TSP heuristics: domination analysis and complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1566378)