Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications

Understand

We extend the work of Narasimhan and Bilmes [30] for minimizing set functions representable as a difference between submodular functions.

• Similar to [30], our new algorithms are guaranteed to monotonically reduce the objective function at every step.
• We empirically and theoretically show that the per-iteration cost of our algorithms is much less than [30], and our algorithms can be used to efficiently minimize a difference between submodular functions under various combinatorial constraints, a problem not previously addressed.
• We provide computational bounds and a hardness result on the mul- tiplicative inapproximability of minimizing the difference between submodular functions.