Faster Parametric Submodular Function Minimization by Exploiting Duality
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915847263485952 |
|---|---|
| author | Gupta, Swati Zhu, Alec |
| author_facet | Gupta, Swati Zhu, Alec |
| contents | Let $f:2^{E} \rightarrow \mathbb{Z}_+$ be a submodular function on a ground set $E = [n]$, and let $P(f)$ denote its extended polymatroid. Given a direction $d \in \mathbb{Z}^n$ with at least one positive entry, the line search problem is to find the largest scalar $λ$ such that $λd \in P(f)$. The best known strongly polynomial-time algorithm for this problem is based on the discrete Newton's method and requires $\tilde{O}(n^2 \log n)\cdot$ SFM time, where SFM is the time for exact submodular function minimization under the value oracle model.
In this work, we study the first weakly polynomial-time algorithms for this problem. We reduce the number of calls to the exact submodular minimization oracle by exploiting a dual formulation of the parametric line search problem and recent advances in cutting plane methods. We obtain a running time of
\[
O\bigl(n^2 \log(nM\|d\|_1)\cdot \text{EO} + n^3 \log(nM\|d\|_1)\bigr) + O(1)\cdot \text{SFM},
\]
where $M = \|f\|_\infty$ and EO is the cost of evaluating $f$ at a set. Note that when $\log \|d\|_1 = O(\log (nM))$, this matches the current best weakly polynomial running time for submodular function minimization [Lee, Sidford, Wong '15], and therefore, one cannot hope to improve this running time. Our approach proceeds by deriving a dual formulation that minimizes the Lovász extension $F$ over a hyperplane intersecting the unit hypercube, and then solving this dual problem approximately via cutting-plane methods, after which we round to the exact intersection using the integrality of $f$ and $d$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_08672 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Faster Parametric Submodular Function Minimization by Exploiting Duality Gupta, Swati Zhu, Alec Optimization and Control Combinatorics 90C25, 90C31 Let $f:2^{E} \rightarrow \mathbb{Z}_+$ be a submodular function on a ground set $E = [n]$, and let $P(f)$ denote its extended polymatroid. Given a direction $d \in \mathbb{Z}^n$ with at least one positive entry, the line search problem is to find the largest scalar $λ$ such that $λd \in P(f)$. The best known strongly polynomial-time algorithm for this problem is based on the discrete Newton's method and requires $\tilde{O}(n^2 \log n)\cdot$ SFM time, where SFM is the time for exact submodular function minimization under the value oracle model. In this work, we study the first weakly polynomial-time algorithms for this problem. We reduce the number of calls to the exact submodular minimization oracle by exploiting a dual formulation of the parametric line search problem and recent advances in cutting plane methods. We obtain a running time of \[ O\bigl(n^2 \log(nM\|d\|_1)\cdot \text{EO} + n^3 \log(nM\|d\|_1)\bigr) + O(1)\cdot \text{SFM}, \] where $M = \|f\|_\infty$ and EO is the cost of evaluating $f$ at a set. Note that when $\log \|d\|_1 = O(\log (nM))$, this matches the current best weakly polynomial running time for submodular function minimization [Lee, Sidford, Wong '15], and therefore, one cannot hope to improve this running time. Our approach proceeds by deriving a dual formulation that minimizes the Lovász extension $F$ over a hyperplane intersecting the unit hypercube, and then solving this dual problem approximately via cutting-plane methods, after which we round to the exact intersection using the integrality of $f$ and $d$. |
| title | Faster Parametric Submodular Function Minimization by Exploiting Duality |
| topic | Optimization and Control Combinatorics 90C25, 90C31 |
| url | https://arxiv.org/abs/2603.08672 |