Maximization Problem for Independence Systems/Greedy Algorithm
Algorithm
Let $\struct{S,\mathscr F}$ be an independence system.
Let $w : S \to \R_{\ge 0}$ be a weight function.
The purpose of this algorithm is to produce a maximal set of $\mathscr F$ with maximum weight for the maximization problem $\struct{\mathscr F, w}$.
The greedy algorithm for the maximization problem $\struct{\mathscr F, w}$ proceeds as follows:
- Step 1: Start with $A_0 = \O$.
- Step 2: Choose $x \in S \setminus A_0$ such that:
- a): $A_0 \cup \set x \in \mathscr F$
- b): $\map w x = \max \set{\map w y : y \in S \setminus A_0 \land A_0 \cup \set y \in \mathscr F}$.
- Step 3: If no such $x$ exists, stop. Otherwise, add $x$ to $A_0$.
- Step 4: Go to Step 2.
The above constitutes an algorithm, for the following reasons:
Finiteness
For each iteration through the algorithm, step 3 is executed, which increases the number of elements in $A_0$ by $1$ if it does not stop.
As $S$ is a finite set the algorithm will terminate after a finite number of iterations.
Definiteness
- Step 1: Trivially definite.
- Step 2: As the elements of $S$ can be arranged in order of weight, there is a definite element (or set of elements) with maximum weight. It is straightforward to select an element $x$ which extends $A_0$ to another set in $\mathscr F$.
- Step 3: Trivially definite.
- Step 4: Trivially definite.
Inputs
The input to this algorithm is the maximization problem $\struct{\mathscr F, w}$.
Outputs
The output to this algorithm is a maximal set of $\mathscr F$.
Effective
Each step of the algorithm is basic enough to be done exactly and in a finite length of time.
Also see
- Greedy Algorithm yields Maximal Set where it is shown that the output from the greedy algorithm for the maximization problem $\struct{\mathscr F, w}$ is a maximal set of $\mathscr F$.
- Greedy Algorithm may not yield Maximum Weight where it is shown that the maximal set of $\mathscr F$ constructed by the greedy algorithm is not guaranteed to be of maximum weight.
- Greedy Algorithm guarantees Maximum Weight iff Matroid where it can be seen that the greedy algorithm only guarantees that the chosen maximal set has maximum weight iff $\struct{S, \mathscr F}$ is a matroid.
Sources
- 1976: Dominic Welsh: Matroid Theory ... (previous) Chapter $19.$ $\S 1.$ The greedy algorithm