Quantum and Classical Algorithms for Approximate Submodular Function Minimization

Understand

Submodular functions are set functions mapping every subset of some ground set of size $n$ into the real numbers and satisfying the diminishing returns property.

• Submodular minimization is an important field in discrete optimization theory due to its relevance for various branches of mathematics, computer science and economics.
• The currently fastest strongly polynomial algorithm for exact minimization [LSW15] runs in time $\widetilde{O}(n^3 \cdot \mathrm{EO} + n^4)$ where $\mathrm{EO}$ denotes the cost to evaluate the function on any set.
• For functions with range $[-1,1]$, the best $\epsilon$-additive approximation algorithm [CLSW17] runs in time $\widetilde{O}(n^{5/3}/\epsilon^{2} \cdot \mathrm{EO})$.