{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-09","reactions":{}}