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

A faster strongly polynomial time algorithm for submodular function minimization

โœ Scribed by James B. Orlin

Publisher
Springer-Verlag
Year
2007
Tongue
English
Weight
212 KB
Volume
118
Category
Article
ISSN
0025-5610

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

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

A Fully Combinatorial Algorithm for Subm
A Fully Combinatorial Algorithm for Submodular Function Minimization
โœ Satoru Iwata ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 115 KB

This paper presents a strongly polynomial algorithm for submodular function minimization using only additions, subtractions, comparisons, and oracle calls for function values.