𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Minimizing a Combinatorial Function

✍ Scribed by Du, Ding Zhu; Hwang, F. K.

Book ID
118212418
Publisher
Society for Industrial and Applied Mathematics
Year
1982
Weight
426 KB
Volume
3
Category
Article
ISSN
0196-5212

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

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.

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