Improved Lower Bounds for Submodular Function Minimization

Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang +1

We provide a generic technique for constructing families of submodular functions to obtain lower bounds for submodular function minimization (SFM). Applying this technique, we prov…