Submodular function minimization gets faster with new algorithm
A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization
Data Structures and Algorithms
Summary
Minimizing submodular functions is an important problem in computer science with many applications, but it can be very slow for large inputs. The authors have created a new method that speeds up this process by running a known algorithm continuously without restarting. This makes solving these problems more efficient, potentially saving time and computing resources. Their improvement builds on earlier methods and enhances the cutting plane technique combined with a special framework for finding connections in data.
What this means in practice
- •For optimization software developers: Implement more efficient submodular minimization routines to speed up large-scale optimization tasks.
- •For machine learning engineers: Improve training performance on models that rely on submodular functions by using faster minimization algorithms.
Authors
Alina Ene, Huy L. Nguyen
Abstract
We give a strongly polynomial time algorithm for submodular function minimization with overall running time $\widetilde{O}(n^{2}\mathsf{EO}+n^{3})$ time, where $\mathsf{EO}$ is the running time of a single evaluation of the function. Our algorithm improves upon the previously fastest strongly polynomial algorithms of Lee et al. (FOCS 2015), Dadush et al. (SODA 2018), and Jiang et al. (SODA 2024) that run in time $\widetilde{O}(n^{3}\mathsf{EO}+n^{4})$. Similarly to prior works, our work combines a cutting plane algorithm with the combinatorial arc-finding framework of Fleischer et al. (JACM 2001). We achieve our faster running time by developing an algorithm that runs the cutting plane method end to end, without restarting after discovering arcs and contracting strongly connected components.