Reviews: Decomposable Submodular Function Minimization: Discrete and Continuous

This paper studies the problem of minimizing a decomposable submodular function. Submodular minimization is a well studied and important problem in machine learning for which there exist algorithms to solve the problem exactly. However, the running time of these algorithms is a high polynomial and they are thus oftentimes not practical. To get around this issue, submodular functions that can be decomposed and written as a sum of submodular functions over a much smaller support (DSFM) are often considered as they often appear in practice. This paper improves the analysis of the fastest algorithms for DSFM by a factor equal to the number of functions in the decomposition.