LogisticsReviewLovász extensionPolymatroidsScratchSummaryLogistics Review Lov´asz extension Polymatroids 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 12 - May 11th, 2011Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 12 - May 11th, 2011 page 1Logistics Review Lov´asz extension Polymatroids Scratch SummaryAnnouncementsOn Final projects. One single page final project updates due nextWednesday, 5/18 at 5:00pm.Again, all submissions must be done electronically, via our drop box.See the 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 12 - May 11th, 2011 page 2Logistics Review Lov´asz extension Polymatroids Scratch SummaryClass Road MapWe need to find one makeup lectures this term.L1 (3/30):L2 (4/1):L3 (4/6):L4 (4/8):L5 (4/13):L6 (4/15):L7 (4/20):L8 (4/27):L9 (4/29):L10 (5/4):L11 (5/6): On SFM, polymatroidmember & greedy, Lov´asz ext.L12 (5/11): Lov´asz ext. +polymatroid props.L13 (5/13):L14 (5/18):L15 (5/20):L16 (5/25):L17 (5/27):L18 (6/1):L19 (6/3):L20: (6/?): (need to findtime/date/place).Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 12 - May 11th, 2011 page 3Logistics Review Lov´asz extension Polymatroids Scratch SummaryTowards SFMRecall the Edmonds matroid partition algorithm, was SFM forr(A) −1k1(A).We now have an algorithm that can do SFM on r(A) − x(A) for anyx ∈ RE+and any matroid rank function..There are three limitations to this:1r(A) is only a matroid rank function (and thus integral) rather than a(possibly non-integral) polymatroidal function.2x is required to be positive x ≥ 0.3This works only for the difference between r and x, but we’d like analgorithm that works for any arbitrary submodular function f , evennon-monotone and/or non-non-increasing/decreasing.It turns out that (2) and (3) are easy to deal with, but (1) tookanother 16 years to solve. In fact, the problem can still be seen asunsolved, if we want a reasonable, scalable, guaranteed low-orderpolynomial algorithm.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 12 - May 11th, 2011 page 4Logistics Review Lov´asz extension Polymatroids Scratch SummaryTowards SFMRecall the Edmonds matroid partition algorithm, was SFM forr(A) −1k1(A).We now have an algorithm that can do SFM on r(A) − x(A) for anyx ∈ RE+and any matroid rank function..There are three limitations to this:1r(A) is only a matroid rank function (and thus integral) rather than a(possibly non-integral) polymatroidal function.2x is required to be positive x ≥ 0.3This works only for the difference between r and x, but we’d like analgorithm that works for any arbitrary submodular function f , evennon-monotone and/or non-non-increasing/decreasing.It turns out that (2) and (3) are easy to deal with, but (1) tookanother 16 years to solve. In fact, the problem can still be seen asunsolved, if we want a reasonable, scalable, guaranteed low-orderpolynomial algorithm.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 12 - May 11th, 2011 page 4Logistics Review Lov´asz extension Polymatroids Scratch SummaryTowards SFMRecall the Edmonds matroid partition algorithm, was SFM forr(A) −1k1(A).We now have an algorithm that can do SFM on r(A) − x(A) for anyx ∈ RE+and any matroid rank function..There are three limitations to this:1r(A) is only a matroid rank function (and thus integral) rather than a(possibly non-integral) polymatroidal function.2x is required to be positive x ≥ 0.3This works only for the difference between r and x, but we’d like analgorithm that works for any arbitrary submodular function f , evennon-monotone and/or non-non-increasing/decreasing.It turns out that (2) and (3) are easy to deal with, but (1) tookanother 16 years to solve. In fact, the problem can still be seen asunsolved, if we want a reasonable, scalable, guaranteed low-orderpolynomial algorithm.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 12 - May 11th, 2011 page 4Logistics Review Lov´asz extension Polymatroids Scratch SummaryTowards SFMRecall the Edmonds matroid partition algorithm, was SFM forr(A) −1k1(A).We now have an algorithm that can do SFM on r(A) − x(A) for anyx ∈ RE+and any matroid rank function..There are three limitations to this:1r(A) is only a matroid rank function (and thus integral) rather than a(possibly non-integral) polymatroidal function.2x is required to be positive x ≥ 0.3This works only for the difference between r and x, but we’d like analgorithm that works for any arbitrary submodular function f , evennon-monotone and/or non-non-increasing/decreasing.It turns out that (2) and (3) are easy to deal with, but (1) tookanother 16 years to solve. In fact, the problem can still be seen asunsolved, if we want a reasonable, scalable, guaranteed low-orderpolynomial algorithm.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 12 - May 11th, 2011 page 4Logistics Review Lov´asz extension Polymatroids Scratch SummaryTowards SFMRecall the Edmonds matroid partition algorithm, was SFM forr(A) −1k1(A).We now have an algorithm that can do SFM on r(A) − x(A) for anyx ∈ RE+and any matroid rank function..There are three limitations to this:1r(A) is only a matroid rank function (and thus integral) rather than a(possibly non-integral) polymatroidal function.2x is required to be positive x ≥ 0.3This works only for the difference between r and x, but we’d like analgorithm that works for any arbitrary submodular function f , evennon-monotone and/or non-non-increasing/decreasing.It turns out that (2) and (3) are easy to deal with, but (1) tookanother 16 years to solve. In fact, the problem can still be seen asunsolved, if we want a reasonable, scalable, guaranteed low-orderpolynomial algorithm.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 12 - May 11th, 2011 page 4Logistics Review Lov´asz extension Polymatroids Scratch SummaryTowards SFMRecall the Edmonds matroid partition algorithm, was SFM forr(A) −1k1(A).We now have an algorithm that can do SFM on r(A) − x(A) for anyx ∈ RE+and any matroid rank function..There are three limitations to this:1r(A) is only a