When the greedy algorithm fails

DOI10.1016/J.DISOPT.2004.03.007MaRDI QIDQ2386197zbMATH OpenOpenAlexFDO

Authors G. Gutin, A. Yeo, Jørgen Bang-Jensen

Publication date 22 August 2005

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2004.03.007

zbMATH Keywords

combinatorial optimizationgreedy algorithmtraveling salesman problem

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4019111
• scientific article; zbMATH DE number 169611
• On the Greedy Solution of Ordering Problems
• scientific article; zbMATH DE number 4149905
• scientific article; zbMATH DE number 3970528

Cites work

• scientific article; zbMATH DE number 1263991 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 2064413 (Why is no real title available?)
• scientific article; zbMATH DE number 1754594 (Why is no real title available?)
• An approximation algorithm for the asymmetric travelling salesman problem with distances one and two
• Anti-matroids
• Domination analysis of some heuristics for the traveling salesman problem
• Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number
• TSP heuristics: domination analysis and complexity
• The Traveling Salesman Problem with Distances One and Two
• Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP

Cited in

(14)

• Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics
• The greedy algorithm for the symmetric TSP
• An auxiliary function method for global minimization in integer programming
• A critical review of discrete filled function methods in solving nonlinear discrete optimization problems
• Minimum number of below average triangles in a weighted complete graph
• Data-driven reduced order modelling for patient-specific hemodynamics of coronary artery bypass grafts with physical and geometrical parameters
• Greedy heuristics with regret, with application to the cheapest insertion algorithm for the TSP
• Discrete optimization algorithms and problems of decision making in a fuzzy environment
• scientific article; zbMATH DE number 4019111 (Why is no real title available?)
• Greedy-type resistance of combinatorial problems
• The neighbor-net algorithm
• A fast randomized algorithm for the heterogeneous vehicle routing problem with simultaneous pickup and delivery
• Algorithms of discrete optimization and their application to problems with fuzzy coefficients
• DNA paired fragment assembly using graph theory

This page was built for publication: When the greedy algorithm fails

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2386197)