Part of Advances in Neural Information Processing Systems 30 (NIPS 2017)
Alina Ene, Huy Nguyen, László A. Végh
This paper investigates connections between discrete and continuous approaches for decomposable submodular function minimization. We provide improved running time estimates for the state-of-the-art continuous algorithms for the problem using combinatorial arguments. We also provide a systematic experimental comparison of the two types of methods, based on a clear distinction between level-0 and level-1 algorithms.