Maximization Problem for Independence Systems

Problem

Let $\struct{S,\mathscr F}$ be an independence system.

Let $w:S \to \R_{\ge 0}$ be a weight function.

The maximization problem $\struct{\mathscr F, w}$ for $\struct{S,\mathscr F}$ is the computational problem to find a subset $A_0$ of $S$ with the properties:

$(1)\quad A_0 \in \mathscr F$

$(2)\quad \map {w^+} {A_0} = \max \set{\map {w^+} A : A \in \mathscr F}$

where $w^+$ is the extended weight function of $w$.

Greedy Algorithm

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.

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) ... (next) Chapter $19.$ $\S 1.$ The greedy algorithm
• 2018: Bernhard H. Korte and Jens Vygen: Combinatorial Optimization: Theory and Algorithms (6th ed.) Chapter $13$ Matroids $\S 13.1$ Independence Systems and Matroids