The traveling salesman problem: new polynomial approximation algorithms and domination analysis

DOI10.1080/02522667.2001.10699482zbMath1049.90078OpenAlexW2045758866MaRDI QIDQ2780838

Abraham P. Punnen

Publication date: 2001

Published in: Journal of Information and Optimization Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/02522667.2001.10699482

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items

The exponential multi-insertion neighborhood for the vehicle routing problem with unit demands ⋮ Upper bounds on ATSP neighborhood size. ⋮ Domination analysis of greedy heuristics for the frequency assignment problem. ⋮ A survey of very large-scale neighborhood search techniques ⋮ TSP tour domination and Hamilton cycle decompositions of regular digraphs ⋮ Further extension of the TSP assign neighborhood ⋮ A class of exponential neighbourhoods for the quadratic travelling salesman problem ⋮ A new ILP-based refinement heuristic for vehicle routing problems ⋮ Domination analysis of some heuristics for the traveling salesman problem

Cites Work

• Improved complexity bound for the maximum cardinality bottleneck bipartite matching problem
• The traveling salesman. Computational solutions for RSP applications
• Relaxed tours and path ejections for the traveling salesman problem
• The Bottleneck Traveling Salesman Problem
• Halin graphs and the travelling salesman problem
• Unnamed Item
• Unnamed Item
• Unnamed Item