Geometric Rescaling Algorithms for Submodular Function Minimization

• 成果类型: Article
• 署名作者: Dadush, Dan; Vegh, Laszlo A.; Zambelli, Giacomo
• 署名单位: University of London; London School Economics & Political Science
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2020.1064
• 发表日期: 2021
• 页码: 1081-1108
• 关键词: COMBINATORIAL

摘要

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. First, 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) center dot EO + n(5))log(nL)). Second, we exhibit a general combinatorial black box approach to turn EL-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) center dot 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 et al., yielding a simplified variant of their O(n(3)log(2) n center dot EO + n(4)log(O(1))n) algorithm.