# 3. Greedy Works!

Recall that from last time, we were dealing with:

- a finite universe of elements \cal U = \{e_1, e_2, \cdots, e_n\}
- a weight function w: \cal U \longrightarrow \mathbb{Q}^{\geqslant 0} that assigns a non-negative weight with every universe element
- oracle access to a family \cal F = \{S_1, \ldots, S_m\} of subsets of \cal U

and we wanted to determine the maximum weight attained by any set in \cal F, where the weight of a set is defined as the sum of the weights of the elements that belong to it.

To this end, we proposed the following greedy algorithm:

Since the greedy algorithm did not work “at large”, we agreed that it might be interesting to impose some constraints on \cal F and see if we could argue that the greedy algorithm works for all families that enjoy some additional structure. After some back and forth, here is what we came up with:

All this sets the stage for the main result that we want to get to:

This result also has an interesting flip side, so to speak. When dealing with set systems that do *not* satisfy the exchange axiom, it turns out that we can adverserially choose a weight function that misleads the greedy algorithm into producing suboptimal output! The intuition is the following: a violation of the exchange axiom in a set system (\cal U, \cal F) amounts to saying the following:

\exists S, T \in \cal F such that |S| > |T| but for all e \in S \setminus T, T \cup \{e\} \notin \cal F.

Now our plan is the following.

We “tempt” greedy into picking all elements in T before anything in S, by making the elements of T just a little heavier than elements in, say, S \setminus T. Note that once greedy chooses all of T, it cannot expand further into S because of the violation above combined with its own committment to navigating with \cal F. So it will skip over all elements of S \setminus T: which is an opportunity for us to create a better optimal solution.

In particular, our goal will be to assign weights to elements in S \setminus T in such a way that w(S) > w(T) in spite of the fact that elements in T are heavier than those in S \setminus T. Here, we can take advantage of the fact that |S| > |T|.

With these ideas in place, can you come up with the adverserial weight function?

This completes the argument for the following fact:

Recall the Dance Classes problem considered in Chapter 1. There is a natural subset system associated with this problem: A set of classes is independent if and only if no two classes overlap. This subset system is not a matroid, because there can be maximal independent sets of different sizes, which violates the exchange property. If we consider a weighted version of the class scheduling problem, where each class is worth a different number of hours, our result above implies that the greedy algorithm will not always find the optimal schedule.

However, this result here does not contradict the correctness of the greedy algorithm for the original unweighted problem; that problem uses a particularly lucky choice of weights (all equal), whereas the claim here is simply that there exists particularly nasty choice of weights that is designed to mislead greedy into making suboptimal choices.