en

0.25

0.5

0.75

1.25

1.5

1.75

2

# Submodularity and Discrete Convexity

Published on Jan 16, 20139020 Views

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

#### Related categories

#### Chapter list

Submodularity and Discrete Convexity00:00

A submodular function00:11

A submodular function: Lemma01:01

A submodular function: Theorem01:46

Distributive Lattices and Posets: Theorem02:27

A simple distributive lattice06:13

Submodular System (D, f) on E - 106:41

Submodular System (D, f) on E - 207:11

Remark08:41

Define a supermodular system09:03

Duality09:20

(D, f): A submodular system on E - 110:34

(D, f): A submodular system on E - 210:58

(D, f): A submodular system on E - 311:27

(D, f): A submodular system on E - 411:45

Polymatroid (Edmonds)12:03

Matroid (Whitney)12:47

Generalized polymatroids (Frank, Hassin) and Base Polyhedra13:22

Theorem (Tomizawa)14:19

Corollary14:53

The Intersection Theorem and Its Equivalents - 116:44

The Intersection Theorem and Its Equivalents - 217:43

The Intersection Theorem and Its Equivalents - 319:13

The Intersection Theorem and Its Equivalents - 420:04

The Intersection Theorem and Its Equivalents - 520:46

The Intersection Theorem and Its Equivalents - 621:46

The Intersection Theorem and Its Equivalents - 722:58

Minimum-Norm Base and SFM - 124:08

Minimum-Norm Base and SFM - 224:33

Minimum-Norm Base and SFM - 326:18

Minimum-Norm Base and SFM - 426:39

Minimum-Norm Base and SFM - 527:35

Minimum-Norm Base and SFM - 628:08

Minimum-Norm Base and SFM - 728:19

Minimum-Norm Base and SFM - 828:45

Minimum-Norm Base and SFM - 929:05

Minimum-Norm Base and SFM - 1030:01

Maximum Weight Base Problem - 131:40

Maximum Weight Base Problem - 232:16

Maximum Weight Base Problem - 333:46

Maximum Weight Base Problem - 435:16

Maximum Weight Base Problem - 536:15

Maximum Weight Base Problem - 636:32

Subgradients and Subdifferentials of Submodular Functions - 136:51

Subgradients and Subdifferentials of Submodular Functions - 239:50

Subgradients and Subdifferentials of Submodular Functions - 340:27

A simplicial division of the plane (triangulation) - 140:55

A simplicial division of the plane (triangulation) - 241:14

Discrete convex functions - 142:02

Discrete convex functions - 242:36

Discrete convex functions - 345:17

Discrete convex functions - 447:10

Discrete convex functions - 548:22

Discrete convex functions - 648:40

Discrete convex functions - 750:36

Discrete convex functions - 850:45

M♮-concave function g51:14

Simultaneous Exchange Axiom for M♮-convex functions51:35

Discrete Separation Theorem (L♮) - 152:06

Discrete Separation Theorem (L♮) - 252:32

Discrete Separation Theorem (L♮) - 352:53

Intersections of subdifferentials and superdifferentials (integral generalized polymatroids) - 153:21

Intersections of subdifferentials and superdifferentials (integral generalized polymatroids) - 253:52

Intersections of subdifferentials and superdifferentials (integral generalized polymatroids) - 354:14

Intersections of subdifferentials and superdifferentials (integral generalized polymatroids) - 454:38

Discrete Fenchel Duality Theorem (Murota) - 155:07

Discrete Fenchel Duality Theorem (Murota) - 255:51

For more information see the following monographs57:12