O'Reilly logo

A Guide to Algorithm Design by Frédéric Vivien, Yves Robert, Anne Benoit

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 3
Greedy algorithms
This chapter explains the reasoning in finding optimal greedy algorithms. The
main feature of a greedy algorithm is that it builds the solution step by step,
and, at each step, it makes a decision that is locally optimal. Throughout
Sections 3.1 to 3.3, we illustrate this principle with several examples and also
outline situations where greedy algorithms are not optimal; taking a good
local decision may prove a bad choice in the end! In Section 3.4, we also cover
matroids, a (mostly theoretical) framework to prove the optimality of greedy
algorithms. All of these techniques are then illustrated with a set of exercises
in Section 3.5, with solutions found in Section 3.6.
3.1 Motivating exam ple: The sports hall
Problem. Let us consider a sports hall in which several events should be
scheduled. The goal is to have as many events as possible, given that two
events cannot occur simultaneously (only one hall). Each event i is character-
ized by its starting ti me s
i
and its ending time e
i
. Two events are compatible
if their time intervals do not overlap. We would like to solve the problem,
i.e., find the maximum number of events that can fit in the sports hall, with
a greedy algorithm.
A first greedy algorithm. The first idea consists of sorting events by
increasing durations e
i
d
i
. At each step, we schedule an event into the
sports hall if it fits, i.e., if it is compatible with events that have already been
scheduled. The idea is that we will be able to accommodate more shorter
events than longer ones. However, we make local decisions at each step of
the algorithm (this is a greedy algorithm!), and it turns out that we can make
decisions that do not lead to the optimal solution. For instance, in the example
of Figure 3.1, the greedy algorithm schedules only the shortest event i, while
the two compatible events j and k would lead to a better solution.
A second greedy algorithm. In order to avoid the problem encountered
in the previous example, we design a new algorithm that sorts events by
53
© 2014 by Taylor & Francis Group, LLC
54 Chapter 3. Greedy algorithms
FIGURE 3.1: The first greedy algorithm is not optimal.
starting times s
i
and then proceeds similarly to the first greedy algorithm. In
the example of Figure 3.1, th is greedy algorithm returns the optimal solution.
However, the local decisions that are made may not be the optimal ones, as
shown in the example of Figure 3.2. Indeed, the algorithm schedules event i
at the first step, and then no other event can be scheduled, while it would be
possible to have eight compatible events. Note th at the first greedy algorithm
would return the optimal solution for this example.
FIGURE 3.2: The second greedy algorithm is not optimal.
A third greedy algorithm. Building upon the first two algorithms, we
observe that it is always a goo d idea to select first events that do not intersect
with many other events. In the first example, events j and k intersect with
only one other event, while event i intersects with two events and is chosen
later; therefore, the new algorithm finds the optimal solution. Similarly in the
second example, event i intersects eight other events, and it is the only event
not to be scheduled. However, this greedy algorithm is still not optimal. We
can build an example in which we force the algorithm to make a bad local
decision. In the example of Figure 3.3, event i is the first to be chosen because
it has the smallest number of intersecting events. However, if we schedule i,
we can have only three compatible events, while we could have a solution with
four compatible events, j, k, l , an d m.
FIGURE 3.3: The third greedy algorithm is not optimal.
© 2014 by Taylor & Francis Group, LLC

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required