Title: Geometric Rescaling Algorithms for Submodular Function Minimization,
Abstract: We present a new class of polynomial-time algorithms for submodular function
minimization (SFM), as well as a unified framework to obtain strongly
polynomial SFM algorithms. Our new algorithms are based on simple iterative
methods for the minimum-norm problem, such as the conditional gradient and the
Fujishige-Wolfe algorithms. We exhibit two techniques to turn simple iterative
methods into polynomial-time algorithms.
Firstly, we use the geometric rescaling technique, which has recently gained
attention in linear programming. We adapt this technique to SFM and obtain a
weakly polynomial bound $O((n^4\cdot EO + n^5)\log (n L))$.
Secondly, we exhibit a general combinatorial black-box approach to turn any
strongly polynomial $\varepsilon L$-approximate SFM oracle into a strongly
polynomial exact SFM algorithm. This framework can be applied to a wide range
of combinatorial and continuous algorithms, including pseudo-polynomial ones.
In particular, we can obtain strongly polynomial algorithms by a repeated
application of the conditional gradient or of the Fujishige-Wolfe algorithm.
Combined with the geometric rescaling technique, the black-box approach
provides a $O((n^5\cdot EO + n^6)\log^2 n)$ algorithm. Finally, we show that
one of the techniques we develop in the paper can also be combined with the
cutting-plane method of Lee, Sidford, and Wong, yielding a simplified variant
of their $O(n^3 \log^2 n \cdot EO + n^4\log^{O(1)} n)$ algorithm.