## Submodularity and Discrete Convexity

author: Satoru Fujishige, Research Institute for Mathematical Sciences, Kyoto University
published: Jan. 16, 2013,   recorded: December 2012,   views: 209
Categories
You might be experiencing some problems with Your Video player.

# Slides

0:00 Slides Submodularity and Discrete Convexity A submodular function A submodular function: Lemma A submodular function: Theorem Distributive Lattices and Posets: Theorem A simple distributive lattice Submodular System (D, f) on E - 1 Submodular System (D, f) on E - 2 Remark Define a supermodular system Duality (D, f): A submodular system on E - 1 (D, f): A submodular system on E - 2 (D, f): A submodular system on E - 3 (D, f): A submodular system on E - 4 Polymatroid (Edmonds) Matroid (Whitney) Generalized polymatroids (Frank, Hassin) and Base Polyhedra Theorem (Tomizawa) Corollary The Intersection Theorem and Its Equivalents - 1 The Intersection Theorem and Its Equivalents - 2 The Intersection Theorem and Its Equivalents - 3 The Intersection Theorem and Its Equivalents - 4 The Intersection Theorem and Its Equivalents - 5 The Intersection Theorem and Its Equivalents - 6 The Intersection Theorem and Its Equivalents - 7 Minimum-Norm Base and SFM - 1 Minimum-Norm Base and SFM - 2 Minimum-Norm Base and SFM - 3 Minimum-Norm Base and SFM - 4 Minimum-Norm Base and SFM - 5 Minimum-Norm Base and SFM - 6 Minimum-Norm Base and SFM - 7 Minimum-Norm Base and SFM - 8 Minimum-Norm Base and SFM - 9 Minimum-Norm Base and SFM - 10 Maximum Weight Base Problem - 1 Maximum Weight Base Problem - 2 Maximum Weight Base Problem - 3 Maximum Weight Base Problem - 2 Maximum Weight Base Problem - 3 Maximum Weight Base Problem - 4 Maximum Weight Base Problem - 5 Maximum Weight Base Problem - 6 Subgradients and Subdifferentials of Submodular Functions - 1 Subgradients and Subdifferentials of Submodular Functions - 2 Subgradients and Subdifferentials of Submodular Functions - 3 A simplicial division of the plane (triangulation) - 1 A simplicial division of the plane (triangulation) - 2 Discrete convex functions - 1 Discrete convex functions - 2 Discrete convex functions - 3 Discrete convex functions - 4 Discrete convex functions - 5 Discrete convex functions - 6 Discrete convex functions - 7 Discrete convex functions - 8 M♮-concave function g Simultaneous Exchange Axiom for M♮-convex functions Discrete Separation Theorem (L♮) - 1 Discrete Separation Theorem (L♮) - 2 Discrete Separation Theorem (L♮) - 3 Intersections of subdifferentials and superdifferentials (integral generalized polymatroids) - 1 Intersections of subdifferentials and superdifferentials (integral generalized polymatroids) - 2 Intersections of subdifferentials and superdifferentials (integral generalized polymatroids) - 3 Intersections of subdifferentials and superdifferentials (integral generalized polymatroids) - 4 Discrete Fenchel Duality Theorem (Murota) - 1 Discrete Fenchel Duality Theorem (Murota) - 2 For more information see the following monographs

# 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.

# Description

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