Geometric Rescaling Algorithms for Submodular Function Minimization

Dan Dadush (), László A. Végh () and Giacomo Zambelli ()
Additional contact information
Dan Dadush: Centrum Wiskunde and Informatica, 1098 XG Amsterdam, Netherlands
László A. Végh: London School of Economics and Political Science, London WC2A 2AE, United Kingdom
Giacomo Zambelli: London School of Economics and Political Science, London WC2A 2AE, United Kingdom

Mathematics of Operations Research, 2021, vol. 46, issue 3, 1081-1108

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. 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 · EO + n 5 ) log ⁡ ( n L ) ) . Second, we exhibit a general combinatorial black box approach to turn ε L -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 · 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 · EO + n 4 log ⁡ O ( 1 ) n ) algorithm.

Keywords: Primary: 90C27; Primary: programming/linear/algorithms; theory; submodular function minimization; gradient methods; rescaling (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2020.1064 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:46:y:2021:i:3:p:1081-1108

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().