Id: arxiv/2603.08672 Url: https://arxiv.org/abs/2603.08672 Tags: math.OC, math.CO Score: 0 Title: Faster Parametric Submodular Function Minimization by Exploiting Duality Domain: math.OC Source: arxiv Authors: Swati Gupta, Alec Zhu Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-03-09 Page: https://delphi.science/r/arxiv/2603.08672 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…