Greedy Algorithm for Matroids
Yassin Tesfaw
Advisor: Professor Nan y Ann Neudauer
Afri an Institutes for Mathemati al S ien es
January 23, 2019
Outlines
◮ De nition of Matroids
◮ Weighted Fun tion
◮ Greedy Algorithm for Matroids
◮ Minimum weighted spanning Tree
◮ Kruskal's Algorithm
◮ Theorem for Greedy Algorithm
2 / 11
De nition of Matroids
De nition
A matroid M is an order pair (E , I) onsisting a nite set E and a
olle tion I of subsets of E satisfying the following three onditions:
(M1) ∅ ∈ I .
(M2) If I ∈ I and I ′ ⊆ I , then I ′ ∈ I .
(M3) If I1 and I2 are in I and |I1 | < |I2 |, then there is an element e of
I2 − I1 su h that I1 ∪ e ∈ I .
Example
Given a set E = {a, b, c} and
I = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}}, then (E , I) is a matroid.
3 / 11
De nition
A matroid (E , I) if it equipped with a weight fun tion w : E → R+ , i.e.,
all weights are positive real numbers. If X ⊆ E then
X
w (X ) = w (x).
x∈X
Example
Consider the graph with the E = {a, b, c, d, e} and their weight under
the subs ript.
a1
◮ I = {∅, a, b, c, ab, ac, bc} is a
matroid on E .
b2 c3 e4
◮ X = {a, c, d} have the weight
9.
d5
4 / 11
Greedy Algorithm for Matroids
Before going to greedy algorithm for matroids,
◮ Minimum weighted spanning tree
◮ Kruskal's Algorithm(1956)
5 / 11
Greedy Algorithm for Matroids
Before going to greedy algorithm for matroids,
◮ Minimum weighted spanning tree
◮ Kruskal's Algorithm(1956)
Let I be a olle tion of subsets of a set E and suppose I satis es (M 1)
and (M 2). Let w be a weighted fun tion and w (∅) = 0. The pair (I, w )
be omes optimization problem as:
5 / 11
Find a maximal member B of I of maximum weight?
The greedy algorithm for the pair (I, w ) pro eeds as follows:
// Maximizing version
1. Set X0 = ∅ and j = 0.
2. If E − Xj ontains an element e su h that Xj ∪ e ∈ I , hoose su h
an element ej+1 of maximum weight, Let Xj+1 = Xj ∪ ej+1 , and go
to (3); otherwise, let Xj = BG and go to (4).
3. Add 1 to j and go to (2).
4. stop.
Example
a1
◮ E = {a, b, c, d, e} and
X0 = ∅.
b2 c3 e4 ◮ Iteration for sele ting
d5 ◮ Xj = BG = {d, e, c}
6 / 11
Theorem for Greedy Algorithm
Theorem
Let I be a olle tion of subsets of set E . Then (E , I) is a matroid if and
only if I satis es the following onditions:
(M1) ∅ ∈ I .
(M2) If I ∈ I and I ′ ⊆ I , then I ′ ∈ I .
(G) For all weighted fun tion w : E −→ R, the greedy algorithm
produ es a maximal member of I of maximum weight.
Proof.
◮ If (E , I) is a matroid M 1 and M 2 holds and so too does (G ).
◮ Now suppose that I satis es (M 1), (M 2) and (G ). We want to
show I satis es (M 3).
7 / 11
Assume the ontrary, that is suppose that I1 , I2 are members of I with
|I1 | < |I2 | su h that I1 ∪ e ∈
/ I for all e ∈ I2 − I1 .
8 / 11
Assume the ontrary, that is suppose that I1 , I2 are members of I with
|I1 | < |I2 | su h that I1 ∪ e ∈
/ I for all e ∈ I2 − I1 .
We have |I1 − I2 | < |I2 − I1 | and I1 − I2 6= ∅, so we hose a positive
number ǫ su h that
0 < (1 + ǫ)|I1 − I2 | < |I2 − I1 | (1)
8 / 11
Assume the ontrary, that is suppose that I1 , I2 are members of I with
|I1 | < |I2 | su h that I1 ∪ e ∈
/ I for all e ∈ I2 − I1 .
We have |I1 − I2 | < |I2 − I1 | and I1 − I2 6= ∅, so we hose a positive
number ǫ su h that
0 < (1 + ǫ)|I1 − I2 | < |I2 − I1 | (1)
De ne w : E → R+ by
2 if e ∈ I1 ∩ I2 ,
1
if e ∈ I1 − I2 ,
|I1 −I2 |
w (e) = 1+ǫ
|I2 −I1 | if e ∈ I2 − I1 ,
0
otherwise
8 / 11
Then
w (BG ) = 2|I1 ∩ I2 | + 1 (2)
9 / 11
Then
w (BG ) = 2|I1 ∩ I2 | + 1 (2)
But by (M2), I2 is ontained in maximal memeber I2′ of I and
w (I2 ) = 2|I1 ∩ I2 | + 1 + ǫ (3)
Hen e from (2) and (3), we dedu e that w (I2′ ) > w (BG ), that the greedy
algorithm fails.
9 / 11
Referen es
◮ (Oxford Graduate Texts in Mathemati s) James G. Oxley - Matroid
Theory-Oxford University Press (1993)
10 / 11
Time for Questions
Thank You
11 / 11