LogisticsReviewMatroid and representationDual MatroidMatroid and GreedyOther Matroid PropertiesScratchSummaryLogistics Review Matroid and representation Dual Matroid Matroid and Greedy Other Matroid Properties Scratch SummaryEE595A – Submodular functions, their optimizationand applications – Spring 2011Prof. Jeff BilmesUniversity of Washington, SeattleDepartment of Electrical EngineeringWinter Quarter, 2011http://ee.washington.edu/class/235/2011wtr/index.htmlLecture 5 - April 13th, 2011Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 5 - April 13th, 2011 page 1Logistics Review Matroid and representation Dual Matroid Matroid and Greedy Other Matroid Properties Scratch SummaryAnnouncementsHW1 is on the web page now, at http://ssli.ee.washington.edu/~bilmes/ee595a_spring_2011/hw1.pdfIt is due, Tuesday, April 26th, 11:45pmAll submissions must be done electronically, via our drop box. Seethe linkhttps://catalyst.uw.edu/collectit/dropbox/bilmes/14888,or look at the homework on the web page.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 5 - April 13th, 2011 page 2Logistics Review Matroid and representation Dual Matroid Matroid and Greedy Other Matroid Properties Scratch SummaryMatroidDefinition 2.1 (Matroid)A set system (E, I) is a Matroid if(I1’) ∅ ∈ I(I2’) ∀I ∈ I, J ⊂ I ⇒ J ∈ I (down-closed)(I3’) ∀I , J ∈ I, with |I| > |J|, then there exists x ∈ I \ J such thatJ ∪ {x} ∈ IProf. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 5 - April 13th, 2011 page 3Logistics Review Matroid and representation Dual Matroid Matroid and Greedy Other Matroid Properties Scratch SummaryMatroidsIn fact, we can use the rank of a matroid for its definition.Theorem 2.2 (Matroid from rank)Let E be a set and let r : 2E→ Z+be a function. Then r(·) defines amatroid with r being its rank function if and only if for all A, B ⊆ E :(R1) ∀A ⊆ E 0 ≤ r(A) ≤ |A| (non-negative cardinality bounded)(R2) r(A) ≤ r(B) whenever A ⊆ B ⊆ E (monotone non-decreasing)(R3) r(A ∪ B) + r (A ∩ B) ≤ r(A) + r(B) forall A, B ⊆ E (submodular)So submodular non-negative integral monotone non-decreasingcardinality bounded is necessary and sufficient to define the matroid.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 5 - April 13th, 2011 page 4Logistics Review Matroid and representation Dual Matroid Matroid and Greedy Other Matroid Properties Scratch SummarySystem of Distinct RepresentativesLet (V , V) be a set system (i.e., V = (Vk: i ∈ I) where Vi⊆ V forall i).A family (vi: i ∈ I) for index set I is said to be a system of distinctrepresentatives of V if ∃ a bijection π : I ↔ I such that vi∈ Vπ(i)and vi6= vjfor all i 6= j.In a system of distinct representatives, there is a requirement for therepresentatives to be distinct.Definition 2.3 (transversal)Given a set system (V , V), a set T ⊆ V is a transversal of V if there is abijection π : T ↔ I such thatx ∈ Vπ(x)for all x ∈ T (1)Note that due to it being a bijection, all of I and T are “covered”(so this makes things distinct).Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 5 - April 13th, 2011 page 5Logistics Review Matroid and representation Dual Matroid Matroid and Greedy Other Matroid Properties Scratch SummaryTransversal Matroid RankTransversal matroid has rankr(A) = minJ⊆I(|V (J) ∩ A| − |J| + |I |) (2)Therefore, this function is submodular.Note that it is a minimum over a set of modular functions. Is thistrue in general?Exercise:Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 5 - April 13th, 2011 page 6Logistics Review Matroid and representation Dual Matroid Matroid and Greedy Other Matroid Properties Scratch SummaryTransversal Matroid RankTransversal matroid has rankr(A) = minJ⊆I(|V (J) ∩ A| − |J| + |I |) (2)Therefore, this function is submodular.Note that it is a minimum over a set of modular functions. Is thistrue in general? Exercise:Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 5 - April 13th, 2011 page 6Logistics Review Matroid and representation Dual Matroid Matroid and Greedy Other Matroid Properties Scratch SummaryMatroid loopsA circuit in a matroids is well defined, a subset A ⊆ E is circuit if itis an inclusionwise minimally dependent set (i.e., if r (A) < |A| andfor any a ∈ A, r(A \ {a}) = |A| − 1).There is no reason in a matroid such an A could not consist of asingle element.Such an {a} is called a loop.In a linear matroid, the only such loop is the value 0, as all non-zerovectors have rank 1.Note, we also say that two elements s, t are said to be parallel if{s, t} is a circuit.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 5 - April 13th, 2011 page 7Logistics Review Matroid and representation Dual Matroid Matroid and Greedy Other Matroid Properties Scratch SummaryMatroid loopsA circuit in a matroids is well defined, a subset A ⊆ E is circuit if itis an inclusionwise minimally dependent set (i.e., if r (A) < |A| andfor any a ∈ A, r(A \ {a}) = |A| − 1).There is no reason in a matroid such an A could not consist of asingle element.Such an {a} is called a loop.In a linear matroid, the only such loop is the value 0, as all non-zerovectors have rank 1.Note, we also say that two elements s, t are said to be parallel if{s, t} is a circuit.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 5 - April 13th, 2011 page 7Logistics Review Matroid and representation Dual Matroid Matroid and Greedy Other Matroid Properties Scratch SummaryMatroid loopsA circuit in a matroids is well defined, a subset A ⊆ E is circuit if itis an inclusionwise minimally dependent set (i.e., if r (A) < |A| andfor any a ∈ A, r(A \ {a}) = |A| − 1).There is no reason in a matroid such an A could not consist of asingle element.Such an {a} is called a loop.In a linear matroid, the only such loop is the value 0, as all non-zerovectors have rank 1.Note, we also say that two elements s, t are said to be parallel if{s, t} is a circuit.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 5 - April 13th, 2011 page 7Logistics Review Matroid and representation Dual Matroid Matroid and Greedy Other Matroid Properties Scratch SummaryMatroid loopsA circuit in a matroids is well defined, a subset A ⊆ E is circuit if itis an inclusionwise minimally dependent set (i.e., if r (A) < |A| andfor any a ∈ A, r(A \ {a}) = |A| − 1).There