Chapter 3

Greedy algorithms

This chapter explains the reasoning in ﬁnding 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., ﬁnd the maximum number of events that can ﬁt in the sports hall, with

a greedy algorithm.

A ﬁrst greedy algorithm. The ﬁrst 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 ﬁts, 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 ﬁrst greedy algorithm is not optimal.

starting times s

i

and then proceeds similarly to the ﬁrst 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 ﬁrst step, and then no other event can be scheduled, while it would be

possible to have eight compatible events. Note th at the ﬁrst 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 ﬁrst two algorithms, we

observe that it is always a goo d idea to select ﬁrst events that do not intersect

with many other events. In the ﬁrst 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 ﬁnds 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 ﬁrst 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

Start Free Trial

No credit card required