Article ID: | iaor20051158 |
Country: | Netherlands |
Volume: | 1 |
Issue: | 2 |
Start Page Number: | 121 |
End Page Number: | 127 |
Publication Date: | Nov 2004 |
Journal: | Discrete Optimization |
Authors: | Bang-Jensen Jrgen, Gutin Gregory, Yeo Anders |
We provide a characterization of the cases when the greedy algorithm may produce the unique worst possible solution for the problem of finding a minimum weight base in an independence system when the weights are taken from a finite range. We apply this theorem to TSP and the minimum bisection problem. The practical message of this paper is that the greedy algorithm should be used with great care, since for many optimization problems its usage seems impractical even for generating a starting solution (that will be improved by a local search or another heuristic).