Advances in Greedy Algorithms

The greedy algorithm is one of the simplest approaches to solve the optizmization
problem in which we want to determine the global optimum of a given function by a
sequence of steps where at each stage we can make a choice among a class of possible
decisions. In the greedy method the choice of the optimal decision is made on the
information at hand without worrying about the effect these decisions may have in the
future. Greedy algorithms are easy to invent, easy to implement and most of the time quite
efficient. However there are many problems that cannot be solved correctly by the greedy
approach. The common example of the greedy concept is the problem of ‘Making Change’
in which we want to make a change of a given amount using the minimum number of US
coins. We can use five different values: dollars (100 cents), quarters (25 cents), dimes (10
cents), nickels (5 cents) and pennies (1 cent). The greedy algorithm is to take the largest
possible amount of coins of a given value starting from the highest one (100 cents). It is easy
to see that the greedy strategy is optimal in this setting, indeed for proving this it suffices to
use the induction principle which works well because in each step either the procedure has
ended or there is at least one coin we can use of the actual value. It means that the problem
has a certain optimal substructure, which makes the greedy algorithm effective. However a
slight modification of ‘Making Change’, e.g. where one value is missing, may turn the
greedy strategy to be the worst choice. Therefore there are obvious limits for using the
greedy method: whenever there is no optimal substructure of the problem we cannot hope
that the greedy algorithm will work. On the other hand there is a lot of problems where the
greedy strategy works unexpectedly well and the purpose of this book is to communicate
various results in this area. The key point is the simplicity of the approach which makes the
greedy algorithm a natural first choice to analyze the given problem. In this book there are
discussed several algorithmic questions in: biology, combinatorics, networking, scheduling
or even pure mathematics, where the greedy algorithm can be used to produce the optimal
or nearly optimal answer.

Download Here