A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization".
Jane: Here's the gist of the paper. The paper presents a strongly polynomial time algorithm for submodular function minimization with an overall running time of O(n 2EO + n 3).
Tom: This result improves upon previously fastest strongly polynomial algorithms, such as those by Lee et al.
Jane: (FOCS 2015), Dadush et al.
Tom: (SODA 2018), and Jiang et al.
Paper summary: Tom: So this paper, "A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization," it’s about finding the best solution for submodular functions really fast. It claims they have a strongly polynomial time algorithm with an overall running time of O of n squared EO plus n cubed.
Jane: That sounds promising because most previous algorithms, like the ones by Lee et al., Dadush et al., and Jiang et al., they ran in time O of n cubed EO plus n four. So this new result is faster than those previously fastest strongly polynomial algorithms >
Lu: The core idea here is combining a cutting plane method with a combinatorial arc-finding framework that was developed by Fleischer et al. back in two thousand one > <ref:2610.25403#pg1>
Meng: So, what’s the main claim then? What makes this algorithm faster than the existing ones we see in production systems? It sounds like it’s about how they handle those cuts and arcs >
Lalam: The paper states that they achieve this speed by developing an algorithm that runs the cutting plane method end to end without restarting after discovering arcs and contracting strongly connected components >
Tom: That sounds like a big deal because restarting things in optimization usually adds a lot of overhead, so running it all through once is key >
Jane: And they also use a barrier function whose center they query and modify to create cuts that reduce the feasible set, which then feeds into this combinatorial part >
Meng: So the naive question here would be, how does this help someone who doesn't read math understand what submodular minimization is in simple terms? It’s about finding the best cut or selection when items have diminishing returns >
Lu: It helps by showing a way to use this structure to find the minimum of the Lovász extension over the unit hypercube using these cuts >
Conclusion: Tom: So, looking at "A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization," it’s really about improving the speed of solving submodular function minimization problems >
Jane: The authors, Alina Ene and Huy L. Nguyen, they are trying to bridge a gap with their algorithm that achieves O of n squared EO plus n cubed running time >
Meng: For someone who deploys models, what does this actually mean for us? Does it mean we can handle much larger sets or more complex functions than we could before? Or is this just theoretical speedup for exact solutions >
Lu: It means the complexity of finding the optimal solution scales better than the O of n cubed EO plus n four that some previous work achieved >
Lalam: The main implication is that they provide a randomized algorithm with high probability, returning an exact minimizer using O of n squared log n function evaluations and an additional time of O of n cubed log O one times n >
Tom: That’s the key number there, so we have this fast way to get the best answer for these types of functions on real-world data sets >
Jane: It shows that by combining the cutting plane method with this end-to-end arc finding structure, you can get a significantly better time complexity for these kinds of problems >
Meng: So, it’s a theoretical speedup that suggests future applications might be feasible on larger instances, assuming the function evaluation cost EO isn't too astronomical >
Lu: It pushes the boundary on what’s achievable in strongly polynomial time for this class of functions >
Boston University · Northeastern University
cs.DS
Submitted: 2026-10-18
Updated: 2026-11-11
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 92/100
The gist: The paper presents a strongly polynomial time algorithm for submodular function minimization with an overall running time of O(n 2EO + n 3).
Key concepts
- Cutting Plane Method
- This technique is used to find the minimum of a complex function by iteratively adding linear constraints (cuts) that exclude non-optimal solutions. In this context, it's applied to the Lovász extension over the unit hypercube, where cuts help narrow down the search space for the optimal set.
- Combinatorial Arc-Finding Framework
- This framework is a method used to discover new connections or 'arcs' within a structure by analyzing its combinatorial properties. The paper integrates this with the cutting plane method to efficiently identify new arcs that improve the solution during the minimization process.
- Certificate Reuse
- A certificate is a piece of information derived from the cutting plane process, specifically identifying a 'thin region.' Instead of restarting the entire process after finding an arc or contracting components, this method reuses this certificate to derive new implications repeatedly until the next stage in the algorithm.
- Arithmetic Bound
- This refers to the complexity related to calculations involving numbers and precision. The paper establishes a deterministic arithmetic bound of $O(n^\omega+1)$ by combining combinatorial data structures for incremental reachability with exact Newton steps for geometric work.
Terminology
Summary
The paper presents a strongly polynomial time algorithm for submodular function minimization with an overall running time of O(n 2EO + n 3). p. 0 This result improves upon previously fastest strongly polynomial algorithms, such as those by Lee et al. p. 0 (FOCS 2015), Dadush et al. p. 0 (SODA 2018), and Jiang et al. p. 0 (SODA 2024), which run in time O(n 3EO + n 4). p. 0 The algorithm achieves this speed by combining a cutting plane method with the combinatorial arc-finding framework developed by Fleischer et al. p. 1 (JACM 2001). p. 0 A key innovation is that the cutting plane method is run end-to-end without restarting after discovering arcs and contracting strongly connected components. p. 0
Theorem 1 establishes a randomized algorithm that returns an exact minimizer of h with high probability in O(n squared n) value oracle calls and a total running time of O(n squared nEO + n cubed O(1)n). p. 1
The algorithm proceeds by applying the cutting plane method to find the minimum of the Lovász extension over the unit hypercube, utilizing a barrier function whose center is queried and modified to produce cuts/hyperplanes that reduce the feasible set. p. 3 This process continues until the feasible set becomes thin, yielding a certificate used by a combinatorial component to identify new arcs. p. 3
The deterministic arithmetic bound has two main components: the combinatorial part employs data structures for maintaining incremental reachability as arcs are added, while the geometric work is handled by exact Newton steps. p. 3 The total arithmetic bound is O(n omega+1). p. 3
Several key aspects of the algorithm contribute to its efficiency:
-
Single Cutting Plane Run: Unlike prior methods that restart the cutting plane method after each dimension reduction, this approach executes only one run from beginning to end with a single barrier function.
-
Certificate Reuse: The certificate obtained from the thin region can be reused to derive implications repeatedly until the next dimension reduction phase.
-
Cheap Implication Generation: Each implication is obtained cheaply using only O(n) queries, and since there are at most O(n 2) implications in total, the total number of queries is bounded.
The algorithm maintains an invariant: For every s at least t, every set X U with hs(X) at most 0 is a closed set in the current implications graph,
where H t is submodular and vanishes at both endpoints. Calibration, which enforces constraints by increasing the parameter t, requires only O(n 2) function evaluations and O(n 3) additional time (Lemma 2). p. 6
The separation oracle constructs a vector, which can be either a graph vector or a greedy vector. p. 9 The total runtime for the combinatorial part is O(n 3), and the geometric work involves exact Newton steps costing O(n omega), leading to a total arithmetic bound of O(n omega+1). p. 4
The algorithm identifies new arcs from the cutting plane certificate using Lemmas 5 and 6. p. 5 The total deterministic time is established as O(n squared n EO) + O(n omega+1). p. 3 A randomized implementation achieves a total time of O(n squared n EO) + O(n 3). p. 1 Furthermore, improving the arithmetic runtime using randomized leverage-score maintenance yields a randomized implementation with a total time of O(n squared n EO) + O(n 3). p. 4 The final cost for the randomized algorithm is O(n squared n EO) + O(n 3). p. 4
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Faster strongly polynomial time minimization of submodular functions can be achieved with an overall running time of Oe(n 2EO + n 3), which is an improvement over previous algorithms running in Oe(n 3EO + n 4).
-
The algorithm can return an exact minimizer of a submodular function using O(n squared log n) value oracle calls and total running time O(n squared log nEO + n cubed logO(1) n), providing a faster bound than previously reported.
-
The system can perform arc extraction by identifying new implications from cutting plane certificates in time bounded by Oe(n 3log(n+2)), which is achieved through specialized data structures for quickly finding terms with large gaps in the certificate.
-
The algorithm can handle graph transformations efficiently, as SCC contractions are managed without restarting the entire cutting plane method, allowing the process to run end-to-end with one barrier function.
-
For complex optimization problems, the system can utilize a randomized implementation that achieves an arithmetic runtime of Oe(n 3) and O(n squared log nEO), offering a probabilistic guarantee for exact solutions with high probability.
-
The system can dynamically adapt to changing constraints by employing an inverse-maintenance interface and leverage-score maintenance to update the basis and Hessian approximations without requiring expensive full matrix inversions after every contraction.
-
The system can efficiently find new optimal solutions after a contraction by using a path-following algorithm that maintains certified centers, where each phase terminates in a constant number of Newton steps with a decrement bounded below 1/8.
Related papers
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles