Geometric rescaling algorithms for submodular function minimization

MaRDI QIDQ4607936zbMATH OpenFDO

Authors Daniel Dadush, Giacomo Zambelli, László A. Végh

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1707.05065, http://dl.acm.org/citation.cfm?id=3175324

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27)

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 algorithms are based on simple iterative methods for the minimum-norm problem, such as the conditional gradient and Fujishige-Wolfe algorithms. We exhibit two techniques to turn simple iterative methods into polynomial-time algorithms. Firstly, we adapt the geometric rescaling technique, which has recently gained attention in linear programming, to SFM and obtain a weakly polynomial bound $O((n^{4}cdotextrmEO+n^5)log(nL))$. Secondly, we exhibit a general combinatorial black-box approach to turn $varepsilonL$-approximate SFM oracles into strongly polynomial exact SFM algorithms. 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 an $O((n^{5}cdotextrmEO+n^6)lo{g}^{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 cite{LSW}, yielding a simplified variant of their $O(n^{3}lo{g}^{2}ncdotextrmEO+n^{4}lo{g}^{O(1)}n)$ algorithm.

Recommendations

• Geometric rescaling algorithms for submodular function minimization
• Improved algorithms for submodular function minimization and submodular flow
• Subquadratic submodular function minimization
• scientific article; zbMATH DE number 7051294

Cited in

(6)

• A note on submodular function minimization by Chubanov's LP algorithm
• Geometric rescaling algorithms for submodular function minimization
• Subquadratic submodular function minimization
• Rescaling algorithms for linear conic feasibility
• Some results about the contractions and the pendant pairs of a submodular system
• Minimizing convex functions with rational minimizers

This page was built for publication: Geometric rescaling algorithms for submodular function minimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4607936)