LogisticsReviewPolymatroidsScratchSummaryLogistics Review 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 13 - May 13th, 2011Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 13 - May 13th, 2011 page 1Logistics Review Polymatroids Scratch SummaryAnnouncementsOn Final projects. One single page final project updates due nextWednesday, 5/18 at 11:45pm.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.Homework 2 is due next Friday night at 11:45pm. All things inlectures marked “exercise”Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 13 - May 13th, 2011 page 2Logistics Review 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): More polymatroids, startlatticesL14 (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 13 - May 13th, 2011 page 3Logistics Review Polymatroids Scratch SummaryA Lecture and a Course by Jack Edmonds, Rome, May23-27, 2011POLYMATROIDSThe talk will sketch an introduction to P, NP, coNP, LP duality, matroids, andsome other foundations of combinatorial optimization theory. A predicate,p(x), is a statement with variable input x. It is said to be in NP when, forany x such that p(x) is true, there is, relative to the bit-size of x, an easyproof that p(x) is true. It is said to be in coNP when ¬p(x) is in NP. Itis said to be in P when there is an easy (i.e., polynomially bounded time)algorithm for deciding whether or not p(x) is true. Of course P impliesNP and coNP. Fifty years ago I sp eculated the converse. Polymatroids area linear programming construction of abstract matroids. We use them todescrib e large classes of concrete predicates (i.e., “problems”) which turnout to be in NP, in coNP, and indeed in P. Failures in trying to place theNP “traveling salesman predicate” in coNP, and successes in placing someclosely related polymatroidal predicates in both NP and coNP and then in P,prompted me to conjecture that (1) the NP traveling salesman predicate isnot in P, and (2) all predicates in both NP and coNP are in P. The conjectureshave become popular, and are both used as practical axioms. I might as wellconjecture that the conjectures have no proofs.Monday, May 23 2011, 11:30Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 13 - May 13th, 2011 page 4Logistics Review Polymatroids Scratch SummaryA Lecture and a Course by Jack Edmonds, Rome, May23-27, 2011POLYMATROIDS ETCETERA: ALGORITHMS AND PRETTYTHEOREMSA variety of combinatorial existence theorems will be proved byalgorithms which tell how to find an instance of what is assertedto exist. Another main purpose will be to introduce polyhedralcombinatorics, which uses systems of linear equations to obtainalgorithms and theorems. Emphasis will be on matroids andpolymatroids with a variety of applications, especially to treesystems and branching systems in networks.Tuesday-Friday, May 24-27 2011, 10:30Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 13 - May 13th, 2011 page 4Logistics Review Polymatroids Scratch SummaryA Lecture and a Course by Jack Edmonds, Rome, May23-27, 2011Both may be seen at http://www.iasi.cnr.it/jack/Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 13 - May 13th, 2011 page 4Logistics Review Polymatroids Scratch SummaryAn extension of fFor any f (even not submodular), we can define an extension in thisway, with˜f (w) =mXi=1λif (Ui) (1)with the Ui’s and sorted order of w defined as above, so thatw =Pmi=1λi1UiTheorem 2.1A function f : 2E→ R is submodular iff its Lov´asz extension˜f of f isconvex.Perhaps we could call this the Edmonds-Lov´asz-Choquet extension?Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 13 - May 13th, 2011 page 5Logistics Review Polymatroids Scratch SummaryAn extension of fFor any f (even not submodular), we can define an extension in thisway, with˜f (w) =mXi=1λif (Ui) (1)with the Ui’s and sorted order of w defined as above, so thatw =Pmi=1λi1UiTheorem 2.1A function f : 2E→ R is submodular iff its Lov´asz extension˜f of f isconvex.Perhaps we could call this the Edmonds-Lov´asz-Choquet extension?Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 13 - May 13th, 2011 page 5Logistics Review Polymatroids Scratch SummaryAn extension of fFor any f (even not submodular), we can define an extension in thisway, with˜f (w) =mXi=1λif (Ui) (1)with the Ui’s and sorted order of w defined as above, so thatw =Pmi=1λi1UiTheorem 2.1A function f : 2E→ R is submodular iff its Lov´asz extension˜f of f isconvex.Perhaps we could call this the Edmonds-Lov´asz-Choquet extension?Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 13 - May 13th, 2011 page 5Logistics Review Polymatroids Scratch SummaryChoquet integralDefinition 2.2Let f be any capacity on E and w ∈ RE+. The Choquet integral (1954)of w w.r.t. f is defined byCf(w) =mXi=1(wei− wei+1)f (Ui) (2)where in the sum, we have sorted and renamed the elements of E so thatwe1≥ we2≥ · · · ≥ wem≥ wem+1= 0, and where Ui= {e1, e2, . . . , ei}.Definition 2.3Given w ∈ RE+, the Lov´asz extension (equivalently Choquet integral) maybe defined as follows:˜f (w)def=Z∞0F (α)dα (3)where the function F is defined as before.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 13 - May 13th, 2011 page 6Logistics Review Polymatroids Scratch SummaryChoquet integralDefinition 2.2Let f be any capacity on E and w ∈ RE+. The Choquet integral (1954)of w w.r.t. f is defined byCf(w) =mXi=1(wei− wei+1)f (Ui) (2)where in the sum, we have sorted and renamed the elements of E so thatwe1≥ we2≥ · · · ≥ wem≥ wem+1= 0, and where Ui= {e1, e2, . . . , ei}.Definition 2.3Given w ∈ RE+, the Lov´asz extension (equivalently Choquet integral) maybe