arXiv:2610.25403 · v2

A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization

首次提交 2026-10-19 00:59

版本更新 2026-11-12 02:32

雷达观测 2026-11-13 14:16

摘要

We give a strongly polynomial time algorithm for submodular function minimization with overall running time $\widetilde{O}(n^{2}\mathsf{EO}+n^{3})$, 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, Sidford, and Wong (FOCS 2015), Dadush, Végh, and Zambelli (SODA 2018), and Jiang, Lee, Song, and Zhang (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 Iwata, Fleischer, and Fujishige (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.