Dominik Farhan

Matroids: Greedy algorithm

problem

We are given a system (X,S)(X, S) and weighting function w:X→Qw: X \rightarrow \mathbb{Q} and define that ww applied on some set as w(A)=∑x∈Aw(x)w(A) = \sum_{x \in A} w(x). We'd like to find the independent set A∈SA\in S that has the heighest possible weights.

We will denote w(i)=wiw(i) = w_i for simplicity. Assume that X={1,…,n}X = \{1, \dots, n\} and that weights are in a non-increasing order, where wmw_m is the last positive weight.

Greedy algorithm

I = set()
for i in range(1, m+1):
    if independence_oracle(I, i):
        I.add(i)

Matroids and greedy

Theorem. Let M=(X,S)M = (X, S) be hereditary non-empty system. Then the greedy algorithm works for all functions ww iff MM is a matroid.
Proof (  ⟹  \implies). By contraposition. If MM is not a matroid it needs to break at least one of the matroid properties:

  1. This case won't happend cause we are assuming MM to be nonepmty.

  2. ∃A,B⊆X\exist A ,B \subseteq X such that A⊆B,B∈S,A∉SA \subseteq B, B \in S, A \notin S. Let's take the following w:

    • wi=2,i∈Aw_i = 2, i \in A
    • wi=1,i∈B∖Aw_i = 1, i \in B\setminus A
    • wi=0,otherwisew_i = 0, otherwise
    Clearly algorithm will skip some element of AA but taking them all and creating BB is optimal, so greedy won't work.

  3. ∃A,B∈S\exists A, B \in S such that ∣A∣<∣B∣|A| < |B| and there is no element in BB which we can add to AA. Let's choose the following weight

    • wi=1+12∣S∣,i∈Aw_i = 1 + \frac{1}{2|S|}, i \in A
    • wi=1,i∈B∖Aw_i = 1, i \in B\setminus A
    • wi=0,otherwisew_i = 0, otherwise
    the greedy will find independent set of weight ∣S∣+1/2|S| + 1/2 but BB is clearly better by at least 1/21/2.

Proof (⟸\Longleftarrow).

Let's denote the characteristic vector of optimal solution z∗z^* and the greedy solution z′z'. Ti={1,…i}T_i = \{1,\dots i\}. We will sum only up to mm but won't write it for the sake of brevity. ∑wizi∗=∑wiz∗(Ti)−wi−1z∗(Ti−1)\sum w_i z_i^* = \sum w_i z^*(T_i) - w_{i-1} z^*(T_{i-1}) =∑wi(z∗(Ti)−z∗(Ti−1))= \sum w_i (z^*(T_i) - z^*(T_{i-1})) =wmz∗(Tm)+∑m−1(wi−wi+1)z∗(Ti)= w_m z^*(T_m) + \sum^{m-1} (w_i - w_{i+1})z^*(T_i) ≤wmr(Tm)+∑m−1(wi−wi+1)r(Ti)\leq w_m r(T_m) + \sum^{m-1} (w_i - w_{i+1})r(T_i) the inequality holds because number of elements in optimum is bounded by the rank and both terms are non-negative so changing z∗z^* for rank gives upper bound. By the greedy algorithm: =wmz′(Tm)+∑m−1(wi−wi+1)z′(Ti)= w_m z'(T_m) + \sum^{m-1} (w_i - w_{i+1})z'(T_i) =∑wizi= \sum w_i z_i

Proof (⟸\Longleftarrow using LP).

Let the primal program be max⁡∑i∈Xwixi\max \sum_{i \in X} w_i x_i s.t. xi≥0\text{s.t. } x_i \geq 0  ∑i∈Axi≤r(A),∀A⊆X\text{ } \sum_{i\in A} x_i \leq r(A),\forall A \subseteq X

Then the dual is min⁡∑A⊆Xr(A)yA\min \sum_{A \subseteq X} r(A) y_A s.t. yA≥0,A⊆X\text{s.t. } y_A \geq 0, A \subseteq X  ∑i∈A,A⊆SyA≥wi,∀i∈X\text{ } \sum_{i \in A, A \subseteq S} y_A \geq w_i, \forall i \in X

Let's take the following for the dual solution:

Now by the complementarity we will show that this is indeed the optimal solution. Let ZZ be the set containing elements of the greedy solution. xi>0  ⟹  ∑i∈A,A⊆XyA=wix_i > 0 \implies \sum_{i \in A, A\subseteq X} y_A = w_i this is true by the choice of the dual solution. yA>0  ⟹  ∑i∈Axi=r(A)y_A > 0 \implies \sum_{i\in A} x_i = r(A) which is the same as : yA>0  ⟹  ∣Z∩A∣=r(A)y_A > 0 \implies |Z \cap A| = r(A) this comes from the way greedy algorithm constructs the solution.

Corollary (Edmonds). Let CC be the convex hull of all characteristic vectors of A∈SA\in S then C=PC = P where MM is the polyhedron representing the matroid: P={xi≥0,∑i∈Axi≤r(A),∀A⊆X}P = \{ x_i \geq 0, \sum_{i\in A} x_i \leq r(A),\forall A \subseteq X \}
Proof.