When the greedy algorithm fails

Joergen Bang-Jensen (jbjimada.sdu.dk)
Gregory Gutin (gutincs.rhul.ac.uk)
Anders Yeo (anderscs.rhul.ac.uk)

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

Keywords: Greedy algorithm; traveling salesman problem; combinatorial optimization

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Approximation Algorithms )

Category 3: Combinatorial Optimization (Meta Heuristics )

Citation: Preprint IMADA, University of Southern Denmark, no. 4 (2003)

Download: [PDF]

Entry Submitted: 03/21/2003
Entry Accepted: 03/21/2003
Entry Last Modified: 03/21/2003

Modify/Update this entry