The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms
From MaRDI portal
Publication:4347415
DOI10.1057/palgrave.jors.2600392zbMath0882.90124OpenAlexW2092501917MaRDI QIDQ4347415
Abraham P. Punnen, Fred Glover
Publication date: 7 August 1997
Published in: Journal of the Operational Research Society (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1057/palgrave.jors.2600392
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)
Related Items (34)
Efficient preprocessing methods for tabu search: an application on asymmetric travelling salesman problem ⋮ Fast Heuristics and Approximation Algorithms ⋮ The Bipartite QUBO ⋮ Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP ⋮ On a new edge function on complete weighted graphs and its application for locating Hamiltonian cycles of small weight ⋮ A new mathematical programming formulation for the single-picker routing problem ⋮ Domination analysis for minimum multiprocessor scheduling ⋮ Greedy-type resistance of combinatorial problems ⋮ Divide and conquer strategies for parallel TSP heuristics ⋮ The bilinear assignment problem: complexity and polynomially solvable special cases ⋮ Transformations of generalized ATSP into ATSP. ⋮ Domination analysis of combinatorial optimization problems. ⋮ Upper bounds on ATSP neighborhood size. ⋮ Hamilton decompositions of regular expanders: applications ⋮ Analysis of 2-Opt Heuristic for the Winner Determination Problem Under the Chamberlin-Courant System ⋮ Unnamed Item ⋮ 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 ⋮ Dominance guarantees for above-average solutions ⋮ Minimum number of below average triangles in a weighted complete graph ⋮ The travelling salesman and the PQ-tree ⋮ The generalized vertex cover problem and some variations ⋮ Construction heuristics for the asymmetric TSP. ⋮ 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 ⋮ A domination algorithm for {0,1}-instances of the travelling salesman problem ⋮ Bilinear Assignment Problem: Large Neighborhoods and Experimental Analysis of Algorithms ⋮ A class of exponential neighbourhoods for the quadratic travelling salesman problem ⋮ A new ILP-based refinement heuristic for vehicle routing problems ⋮ Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number ⋮ Domination analysis of some heuristics for the traveling salesman problem
This page was built for publication: The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms
