Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP

DOI10.1016/S0166-218X(01)00195-0zbMath1004.68121OpenAlexW2092292680WikidataQ56067388 ScholiaQ56067388MaRDI QIDQ1348379

Alexey Zverovich, Anders Yeo, Gregory Gutin

Publication date: 15 May 2002

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

Full work available at URL: https://doi.org/10.1016/s0166-218x(01)00195-0

zbMATH Keywords

greedy algorithmnearest neighbor algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (19)

On a new edge function on complete weighted graphs and its application for locating Hamiltonian cycles of small weight ⋮ Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics ⋮ When the greedy algorithm fails ⋮ Greedy-type resistance of combinatorial problems ⋮ A multi-agent based self-adaptive genetic algorithm for the long-term car pooling problem ⋮ On global integer extrema of real-valued box-constrained multivariate quadratic functions ⋮ Domination analysis of combinatorial optimization problems. ⋮ Unnamed Item ⋮ Domination analysis of greedy heuristics for the frequency assignment problem. ⋮ The correlation of gene expression and co-regulated gene patterns in characteristic KEGG pathways ⋮ A meta-heuristic for capacitated green vehicle routing problem ⋮ Dominance guarantees for above-average solutions ⋮ Memetic algorithms: The polynomial local search complexity theory perspective ⋮ A fast randomized algorithm for the heterogeneous vehicle routing problem with simultaneous pickup and delivery ⋮ Can the agent with limited information solve travelling salesman problem? ⋮ Distributed resource allocation with binary decisions via Newton-like neural network dynamics ⋮ A domination algorithm for {0,1}-instances of the travelling salesman problem ⋮ Approximation algorithms with constant ratio for general cluster routing problems ⋮ Anti-matroids

Uses Software

• TSPLIB

Cites Work

• Unnamed Item
• Unnamed Item
• The traveling salesman. Computational solutions for RSP applications
• Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number
• Domination analysis of some heuristics for the traveling salesman problem
• The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms
• Construction heuristics for the asymmetric TSP.
• TSP tour domination and Hamilton cycle decompositions of regular digraphs

This page was built for publication: Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP