en-de
en-es
en-fr
en-sl
en
en-zh
0.25
0.5
0.75
1.25
1.5
1.75
2
Polymatroids and Submodularity
Published on Jan 25, 20128951 Views
Many polytime algorithms have now been presented for minimizing a submodular function f(S) over the subsets S of a finite set E. We provide a tutorial in (somewhat hidden) theoretical foundations of t
Related categories
Chapter list
Polymatroids and Submodularity00:00
Outline01:29
Duality Theorem05:12
A theory is called a ‘good characterization’ of p(x) when it states how p(x) is in NP∩coNP.06:19
You know15:29
Integer polymatroid18:42
For any vectors x and y in Z+, ...22:23
Polymatroid function26:01
Theorem35:27
There are too many inequalities36:57
Greedy Vertex Theorem38:55
The Greedy Algorithm42:32
Another form of the Greedy Alg Thm.45:48
The Integer Polymatroid Intersection Theorem49:34
Optional. The facets of a polymatroid.52:36
The Matroid Polytope Intersection Theorem56:15
The Matroid Cardinality Intersection Theorem57:26
Example Application58:42
Matroid Partitioning, another application of Matroid Intersection01:02:19
Proof of (4) from The Matroid Intersection Theorem01:07:08
Optimum System of k edge-disjoint branchings01:15:18
Other systems?01:24:17