en
0.25
0.5
0.75
1.25
1.5
1.75
2
Submodularity and Discrete Convexity
Published on Jan 16, 20139027 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