When the greedy algorithm fails

When the greedy algorithm fails

0.00 Avg rating0 Votes
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: , ,
Abstract:

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).

Reviews

Required fields are marked *. Your email address will not be published.