Article ID: | iaor20071401 |
Country: | Netherlands |
Volume: | 3 |
Issue: | 4 |
Start Page Number: | 288 |
End Page Number: | 298 |
Publication Date: | Dec 2006 |
Journal: | Discrete Optimization |
Authors: | Margot Franois, Bendall Gareth |
Keywords: | heuristics |
This paper gives a sufficient condition for a combinatorial problem to be greedy-type resistant, i.e. such that, on some instances of the problem, any greedy-type algorithm will output the unique worst possible solution. The condition is used to show that the Equipartition, the