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