Material Detail

Submodularity and Discrete Convexity

Submodularity and Discrete Convexity

This video was recorded at NIPS Workshops, Lake Tahoe 2012. The present talk is a tutorial one and gives some essence of submodular functions and discrete convexity. The contents of my talk will be the following: Submodular and Supermodular Functions Submodularity Distributive Lattices and Posets (Birkhoff-Iri) Submodular Systems and Supermodular Systems Submodular polyhedron and Base Polyhedron Duality Polymatroids and Matroids Generalized Polymatroids Characterization by Edge-vectors Crossing- and Intersecting-submodular Functions Intersection Theorem and Its Equivalents Intersection Theorem Discrete Separation Theorem Fenchel Duality Theorem Minkowski Sum Theorem Minimum-Norm Base and Submodular Function Minimization Lexicographically Optimal Base Minimum-Norm Base Submodular Function Minimization Maximum Weight Base Problem Greedy Algorithm Lovasz extension Subgradients and Subdifferentials of Submodular Functions Discrete Convex Analysis L♮-convex Functions M♮-convex Functions Discrete Separation Theorem Fenchel Duality Theorem


  • User Rating
  • Comments
  • Learning Exercises
  • Bookmark Collections
  • Course ePortfolios
  • Accessibility Info

More about this material


Log in to participate in the discussions or sign up if you are not already a MERLOT member.