scientific article; zbMATH DE number 4019111
From MaRDI portal
Publication:3030863
[For the entire collection see Zbl 0615.00012.] The greedy heuristic is frequently used to find a ``solution in a variety of combinatorial optimization problems. Its appeal as an efficient algorithm which clearly works in a number of instances and which is based on reasonable assumptions is shown to be superficial by constructions for \(n\times n\) matrices where it produces the worst possible approximation of the optimum assignment or travelling salesman's tour. How could something that looks so good be so bad?
Recommendations
Cited in
(7)- Intractability and analysis of heuristics for discrete optimization. II
- Combinatorial optimization algorithms combining greedy strategies with a limited search procedure
- Greedy algorithm for local heating problem
- When the greedy algorithm fails
- Interpolating greedy and reluctant algorithms
- The greedy algorithm for the symmetric TSP
- Greedy heuristics with regret, with application to the cheapest insertion algorithm for the TSP
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3030863)