TSP heuristics: domination analysis and complexity
From MaRDI portal
Publication:1566378
DOI10.1007/s00453-002-0986-1zbMath1060.90075OpenAlexW1601856531MaRDI QIDQ1566378
Santosh N. Kabadi, Margot, François, Abraham P. Punnen
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
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items (19)
Fast Heuristics and Approximation Algorithms ⋮ The Bipartite QUBO ⋮ Novel concave hull-based heuristic algorithm for TSP ⋮ When the greedy algorithm fails ⋮ Domination analysis for minimum multiprocessor scheduling ⋮ Greedy-type resistance of combinatorial problems ⋮ The bilinear assignment problem: complexity and polynomially solvable special cases ⋮ Transformations of generalized ATSP into ATSP. ⋮ Domination analysis of combinatorial optimization problems. ⋮ Domination analysis of greedy heuristics for the frequency assignment problem. ⋮ 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 ⋮ Minimum number of below average triangles in a weighted complete graph ⋮ Symmetric weight constrained traveling salesman problem: Local search ⋮ Extended neighborhood: Definition and characterization ⋮ Worst case analysis of max-regret, greedy and other heuristics for multidimensional assignment and traveling salesman problems ⋮ A domination algorithm for {0,1}-instances of the travelling salesman problem ⋮ Approximation algorithms with constant ratio for general cluster routing problems ⋮ Anti-matroids
This page was built for publication: TSP heuristics: domination analysis and complexity
