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

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

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

• 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
• 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?)
• Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number
• The Traveling Salesman Problem with Distances One and Two
• Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP
• TSP heuristics: domination analysis and complexity

Cited in

(15)

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

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)