Faster Parametric Submodular Function Minimization by Exploiting Duality
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2603.08672
curl -X POST /api/v1/records/arxiv/2603.08672/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.08672/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'