LogisticsReviewMost Violated InequalityA Digression??Matroid PartitioningScratchSummaryLogistics Review Most Violated Inequality A Digression?? Matroid Partitioning 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 8 - April 27th, 2011Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 8 - April 27th, 2011 page 1Logistics Review Most Violated Inequality A Digression?? Matroid Partitioning Scratch SummaryAnnouncementsHW1 was due last night.HW2 should be ready by Friday night (I’ll send email when ready).Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 8 - April 27th, 2011 page 2Logistics Review Most Violated Inequality A Digression?? Matroid Partitioning Scratch SummaryPolymatroidal polyhedron (or a “polymatroid”)Definition 2.1 (polymatroid)A polymatroid is a compact set P ⊆ RE+satisfying10 ∈ P2If y ≤ x ∈ P then y ∈ P (called down monotone).3For any x ∈ RE+, any maximal vector y ∈ P with y ≤ x (called aP-basis of x), has the same component sum y(E). That is for anytwo maximal vectors y1, y2∈ P, we have y1(E) = y2(E).Another way of saying this is that a polymatroid is a compact setthat is zero containing, down monotone, and any maximal vector yin P, bounded by another vector x, has the same vector rank.Compare with the definition of a matroid: a set system that isempty-set containing, down closed, and any maximal set I in I,bounded by another set A, has the same matroid rank.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 8 - April 27th, 2011 page 3Logistics Review Most Violated Inequality A Digression?? Matroid Partitioning Scratch SummaryPolymatroidal polyhedron (or a “polymatroid”)Definition 2.1 (polymatroid)A polymatroid is a compact set P ⊆ RE+satisfying10 ∈ P2If y ≤ x ∈ P then y ∈ P (called down monotone).3For any x ∈ RE+, any maximal vector y ∈ P with y ≤ x (called aP-basis of x), has the same component sum y(E). That is for anytwo maximal vectors y1, y2∈ P, we have y1(E) = y2(E).Another way of saying this is that a polymatroid is a compact setthat is zero containing, down monotone, and any maximal vector yin P, bounded by another vector x, has the same vector rank.Compare with the definition of a matroid: a set system that isempty-set containing, down closed, and any maximal set I in I,bounded by another set A, has the same matroid rank.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 8 - April 27th, 2011 page 3Logistics Review Most Violated Inequality A Digression?? Matroid Partitioning Scratch SummaryPolymatroidal polyhedron (or a “polymatroid”)Definition 2.1 (polymatroid)A polymatroid is a compact set P ⊆ RE+satisfying10 ∈ P2If y ≤ x ∈ P then y ∈ P (called down monotone).3For any x ∈ RE+, any maximal vector y ∈ P with y ≤ x (called aP-basis of x), has the same component sum y(E). That is for anytwo maximal vectors y1, y2∈ P, we have y1(E) = y2(E).Another way of saying this is that a polymatroid is a compact setthat is zero containing, down monotone, and any maximal vector yin P, bounded by another vector x, has the same vector rank.Compare with the definition of a matroid: a set system that isempty-set containing, down closed, and any maximal set I in I,bounded by another set A, has the same matroid rank.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 8 - April 27th, 2011 page 3Logistics Review Most Violated Inequality A Digression?? Matroid Partitioning Scratch SummaryPolymatroidal polyhedron (or a “polymatroid”)Definition 2.1 (polymatroid)A polymatroid is a compact set P ⊆ RE+satisfying10 ∈ P2If y ≤ x ∈ P then y ∈ P (called down monotone).3For any x ∈ RE+, any maximal vector y ∈ P with y ≤ x (called aP-basis of x), has the same component sum y(E). That is for anytwo maximal vectors y1, y2∈ P, we have y1(E) = y2(E).Another way of saying this is that a polymatroid is a compact setthat is zero containing, down monotone, and any maximal vector yin P, bounded by another vector x, has the same vector rank.Compare with the definition of a matroid: a set system that isempty-set containing, down closed, and any maximal set I in I,bounded by another set A, has the same matroid rank.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 8 - April 27th, 2011 page 3Logistics Review Most Violated Inequality A Digression?? Matroid Partitioning Scratch SummaryPolymatroid function and its polyhedron.Definition 2.2A polymatroid function is a real-valued function f defined on subsets of Ewhich is normalized, non-decreasing, and submodular. That is we have1f (∅) = 0 (normalized)2f (A) ≤ f (B) for any A ⊆ B ⊆ E (monotone non-decreasing)3f (A ∪ B) + f (A ∩ B) ≤ f (A) + f (B) for any A, B ⊆ E (submodular)We can define the polyhedron Pfassociated with a polymatroid functionas followsPf=ny ∈ RE+: y(A) ≤ f (A) for all A ⊆ Eo(1)=ny ∈ RE: y ≥ 0, y(A) ≤ f (A) for all A ⊆ Eo(2)Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 8 - April 27th, 2011 page 4Logistics Review Most Violated Inequality A Digression?? Matroid Partitioning Scratch SummaryA polymatroid function’s polyhedron is a polymatroid.Theorem 2.3Let f be a polymatroid function defined on subsets of E . For anyx ∈ RE+, and any Pf-basis yxof x, we have that the component sum of yismax (y(E) : y ≤ x, y ∈ Pf) = yx(E) = min (x(A) + f (E \ A) : A ⊆ E)(3)As a consequence, Pfis a polymatroid.Therefore, by taking elements E \ A to be zero in x, we candefine/recover the submodular function from the polymatroid polyhedronvia the following:f (A) = max {y (A) : y ∈ Pf} (4)Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 8 - April 27th, 2011 page 5Logistics Review Most Violated Inequality A Digression?? Matroid Partitioning Scratch SummaryA polymatroid function’s polyhedron is a polymatroid.Theorem 2.3Let f be a polymatroid function defined on subsets of E . For anyx ∈ RE+, and any Pf-basis yxof x, we have that the component sum of yismax (y(E) : y ≤ x, y ∈ Pf) = yx(E) = min (x(A) + f (E \ A) : A ⊆ E)(3)As a consequence, Pfis a polymatroid.Therefore, by taking elements E \ A to be zero in x, we candefine/recover the submodular function from the polymatroid