2
$\begingroup$

Many people on different articles suggests that if an optimization problem has a greedy solution, the underlying structure must have matroid property.

I was trying to understand this. So far, I was able to prove that for,

  1. Maximum sum of m integers among n integer.
  2. Minimum spanning tree.

However, The classical greedy algorithm Activity Selection seems to fail having both independence and base exchange property.

Let, E = {1-3, 2-4, 3-5, 4-6, 5-7}

Now, Take two independent set, I = {2-4, 4-6} and J = {1-3, 3-5, 5-7}

There is no activity in J which can extend I. Which fails the independence exchange property of matroid, if I understood it correctly. Thus, it is not matroid and shouldn't have a greedy algorithms. But this problem has a greedy solution.

Where am I wrong?

$\endgroup$
1
$\begingroup$

Suppose that $\mathcal{F}$ is a nonempty collection of subsets of a finite set $U$ satisfying the following axiom:

If $A \in \mathcal{F}$ and $B \subseteq A$ then $B \in \mathcal{F}$.

Consider the following algorithm, which gets as input a weight function $w\colon U \to \mathbb{R}_+$ (here $\mathbb{R}_+$ consists of all positive reals):

  1. Set $S \gets \emptyset$.
  2. While there exists an element $x \notin S$ such that $S \cup \{x\} \in \mathcal{F}$:

    • Let $x$ be an element of maximum weight among $\{ x : x \notin S \text{ and } S \cup \{x\} \in \mathcal{F} \}$.
    • Set $S \gets S \cup \{x\}$.
  3. Return $S$.

We say that the algorithm is valid for $w$ if it returns a set $S$ maximizing $\sum_{x \in S} w(x)$ among all $S \in \mathcal{F}$.

Theorem. The algorithm is valid for all $w\colon U \to \mathbb{R}^+$ iff $\mathcal{F}$ is a matroid.

You can find the proof of this theorem in lecture notes and in textbooks.

The algorithm given above is a specific greedy algorithm. This specific greedy algorithm is optimal if and only if the set system is a matroid. However, the (informal) notion of greedy algorithms encompasses more than just this specific algorithm. The theorem above doesn't apply to these algorithms.

In the two good examples you consider, the corresponding greedy algorithms (or at least one of their variants) are instances of the algorithm above. The same isn't true for the algorithm for your bad example.

For a formalized notion of "greedy-like" algorithms, consult (Incremental) priority algorithms by Borodin, Nielsen, and Rackoff. You can see that is is much more general than the simple algorithm stated above.

Another relevant notion is that of greedoid, for which a theorem similar to the one stated above does hold (see Wikipedia for details).

$\endgroup$
  • $\begingroup$ I was reading matroid theory for preparation to read a book on greediod. So, there are greedy algorithm which works on structure other than matroid! But, All matroid can be optimized using the specific greedy algorithm! $\endgroup$ – silentboy Mar 9 '18 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.