๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Minimizing symmetric submodular functions

โœ Scribed by Maurice Queyranne

Publisher
Springer-Verlag
Year
1998
Tongue
English
Weight
669 KB
Volume
82
Category
Article
ISSN
0025-5610

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

A note on the minimization of symmetric
A note on the minimization of symmetric and general submodular functions
โœ H Narayanan ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 131 KB

In this paper we relate the minimization problems for general submodular functions and symmetric submodular functions. We characterize the contractions and restrictions of symmetric submodular functions. The latter we show to be the same as posimodular functions. Finally, we prove the equivalence of

Submodular function minimization
Submodular function minimization
โœ Satoru Iwata ๐Ÿ“‚ Article ๐Ÿ“… 2007 ๐Ÿ› Springer-Verlag ๐ŸŒ English โš– 302 KB
A Combinatorial Algorithm Minimizing Sub
A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time
โœ Alexander Schrijver ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 108 KB

We give a strongly polynomial-time algorithm minimizing a submodular function f given by a value-giving oracle. The algorithm does not use the ellipsoid method or any other linear programming method. No bound on the complexity of the values of f is needed to be known a priori. The number of oracle c