Faster Parametric Submodular Function Minimization by Exploiting Duality

Swati Gupta, Alec Zhu

Let $f:2^E\to {\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$ wi…