Submodularity and Discrete Convexity

author: Satoru Fujishige, Research Institute for Mathematical Sciences, Kyoto University
published: Jan. 16, 2013,   recorded: December 2012,   views: 8957


Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


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:

  1. Submodular and Supermodular Functions
    1. Submodularity
    2. Distributive Lattices and Posets (Birkhoff-Iri)
  2. Submodular Systems and Supermodular Systems
    1. Submodular polyhedron and Base Polyhedron
    2. Duality
    3. Polymatroids and Matroids
    4. Generalized Polymatroids
    5. Characterization by Edge-vectors
    6. Crossing- and Intersecting-submodular Functions
  3. Intersection Theorem and Its Equivalents
    1. Intersection Theorem
    2. Discrete Separation Theorem
    3. Fenchel Duality Theorem
    4. Minkowski Sum Theorem
  4. Minimum-Norm Base and Submodular Function Minimization
    1. Lexicographically Optimal Base
    2. Minimum-Norm Base
    3. Submodular Function Minimization
  5. Maximum Weight Base Problem
    1. Greedy Algorithm
    2. Lovasz extension
    3. Subgradients and Subdifferentials of Submodular Functions
  6. Discrete Convex Analysis
    1. L♮-convex Functions
    2. M♮-convex Functions
    3. Discrete Separation Theorem
    4. Fenchel Duality Theorem

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: