A combinatorial algorithm minimizing submodular functions in strongly polynomial time
A Schrijver - Journal of Combinatorial Theory, Series B, 2000 - Elsevier
Journal of Combinatorial Theory, Series B, 2000•Elsevier
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 calls is bounded by a polynomial in the size of the underlying
set.
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 calls is bounded by a polynomial in the size of the underlying
set.
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 calls is bounded by a polynomial in the size of the underlying set.
Elsevier
