Worst case analysis of max-regret, greedy and other heuristics for multidimensional assignment and traveling salesman problems

DOI10.1007/s10732-007-9033-3zbMath1173.90512OpenAlexW2012738417MaRDI QIDQ1009187

Jing Huang, Gregory Gutin, Boris I. Goldengorin

Publication date: 31 March 2009

Published in: Journal of Heuristics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10732-007-9033-3

zbMATH Keywords

traveling salesman problemdomination analysismultidimensional assignment problemgreedy heuristics

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (6)

Extending single tolerances to set tolerances ⋮ Global tolerances in the problems of combinatorial optimization with an additive objective function ⋮ Extremal values of global tolerances in combinatorial optimization with an additive objective function ⋮ On a property of a three-dimensional matrix ⋮ Local search heuristics for the multidimensional assignment problem ⋮ Multidimensional assignment problem for multipartite entity resolution

Uses Software

• LKH

Cites Work

• Greedy-type resistance of combinatorial problems
• Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking
• Domination analysis of greedy heuristics for the frequency assignment problem.
• TSP heuristics: domination analysis and complexity
• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• 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 traveling salesman problem and its variations
• Tracking elementary particles near their primary vertex: A combinatorial approach
• An Algorithm for the Three-Index Assignment Problem
• The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms
• Letter to the Editor—The Multidimensional Assignment Problem
• Construction heuristics for the asymmetric TSP.
• A set of greedy randomized adaptive local search procedure (GRASP) implementations for the multidimensional assignment problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Worst case analysis of max-regret, greedy and other heuristics for multidimensional assignment and traveling salesman problems