Graph Cuts with Interacting Edge Costs - Examples, Approximations, and Algorithms

Stefanie Jegelka, Jeff Bilmes

We study an extension of the classical graph cut problem, wherein we replace the modular (sum of edge weights) cost function by a submodular set function defined over graph edges.…