LogisticsReviewPolyhedraMatroid PolytopeScratchSummaryLogistics Review Polyhedra Matroid Polytope Scratch SummaryEE595A – Submodular functions, their optimizationand applications – Spring 2011Prof. Jeff BilmesUniversity of Washington, SeattleDepartment of Electrical EngineeringSpring Quarter, 2011http://ssli.ee.washington.edu/~bilmes/ee595a_spring_2011/Lecture 6 - April 15th, 2011Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 6 - April 15th, 2011 page 1Logistics Review Polyhedra Matroid Polytope Scratch SummaryAnnouncementsReminder, HW1 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 6 - April 15th, 2011 page 2Logistics Review Polyhedra Matroid Polytope Scratch SummaryMatroid and the greedy algorithmLet I be a set of subsets of E that is down-closed. Consider anon-negative modular weight function w : E → R+, and we want tofind the A ∈ I that maximizes w(A).Greedy algorithm: Set A = ∅, and repeatedly choose y ∈ E \ A suchthat A ∪ {y} ∈ I with w(y) as large as possible, stopping when nosuch y exists.Theorem 2.1Let I be a non-empty collection of subsets of a set E, down-closed (i.e.,an independence system). Then the pair (E, I) is a matroid if and only iffor each weight function w ∈ RE+, the greedy algorithm leads to a setI ∈ I of maximum weight w(I ).Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 6 - April 15th, 2011 page 3Logistics Review Polyhedra Matroid Polytope Scratch SummaryMatroid and greedyAs given, the theorem asked for a modular function w ∈ RE+.This will not only return an independent set, but it will return abase if we keeping going even if the weights are 0.If we don’t want elements with weight 0, we can stop once (and if)the weight hits zero, thus giving us a maximum weight independentset.We don’t need non-negativity, we can use any w ∈ REand keepgoing until we have a base.If we stop at a negative value, we’ll once again get a maximumweight independent set.We can instead do as small as possible thus giving us a minimumweight independent set/base.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 6 - April 15th, 2011 page 4Logistics Review Polyhedra Matroid Polytope Scratch SummaryMatroid and greedyAs given, the theorem asked for a modular function w ∈ RE+.This will not only return an independent set, but it will return abase if we keeping going even if the weights are 0.If we don’t want elements with weight 0, we can stop once (and if)the weight hits zero, thus giving us a maximum weight independentset.We don’t need non-negativity, we can use any w ∈ REand keepgoing until we have a base.If we stop at a negative value, we’ll once again get a maximumweight independent set.We can instead do as small as possible thus giving us a minimumweight independent set/base.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 6 - April 15th, 2011 page 4Logistics Review Polyhedra Matroid Polytope Scratch SummaryMatroid and greedyAs given, the theorem asked for a modular function w ∈ RE+.This will not only return an independent set, but it will return abase if we keeping going even if the weights are 0.If we don’t want elements with weight 0, we can stop once (and if)the weight hits zero, thus giving us a maximum weight independentset.We don’t need non-negativity, we can use any w ∈ REand keepgoing until we have a base.If we stop at a negative value, we’ll once again get a maximumweight independent set.We can instead do as small as possible thus giving us a minimumweight independent set/base.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 6 - April 15th, 2011 page 4Logistics Review Polyhedra Matroid Polytope Scratch SummaryMatroid and greedyAs given, the theorem asked for a modular function w ∈ RE+.This will not only return an independent set, but it will return abase if we keeping going even if the weights are 0.If we don’t want elements with weight 0, we can stop once (and if)the weight hits zero, thus giving us a maximum weight independentset.We don’t need non-negativity, we can use any w ∈ REand keepgoing until we have a base.If we stop at a negative value, we’ll once again get a maximumweight independent set.We can instead do as small as possible thus giving us a minimumweight independent set/base.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 6 - April 15th, 2011 page 4Logistics Review Polyhedra Matroid Polytope Scratch SummaryMatroid and greedyAs given, the theorem asked for a modular function w ∈ RE+.This will not only return an independent set, but it will return abase if we keeping going even if the weights are 0.If we don’t want elements with weight 0, we can stop once (and if)the weight hits zero, thus giving us a maximum weight independentset.We don’t need non-negativity, we can use any w ∈ REand keepgoing until we have a base.If we stop at a negative value, we’ll once again get a maximumweight independent set.We can instead do as small as possible thus giving us a minimumweight independent set/base.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 6 - April 15th, 2011 page 4Logistics Review Polyhedra Matroid Polytope Scratch SummaryMatroid and greedyAs given, the theorem asked for a modular function w ∈ RE+.This will not only return an independent set, but it will return abase if we keeping going even if the weights are 0.If we don’t want elements with weight 0, we can stop once (and if)the weight hits zero, thus giving us a maximum weight independentset.We don’t need non-negativity, we can use any w ∈ REand keepgoing until we have a base.If we stop at a negative value, we’ll once again get a maximumweight independent set.We can instead do as small as possible thus giving us a minimumweight independent set/base.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 6 - April 15th, 2011 page 4Logistics Review Polyhedra Matroid Polytope Scratch SummaryConvex PolyhedraConvex polyhedra a large topic, we will only draw what we need.Definition 3.1A subset P ⊆ REis a polyhedron if there exists an m × n matrix A andvector b ∈ RE(for some m ≥