Cooperative Cuts: Graph Cuts with Submodular Edge Weights
Stefanie Jegelka, Jeffrey A. Bilmes · MPG.PuRe (Max Planck Society) · 2010
Abstract. We introduce Cooperative cut, a minimum-cost graph cut with a submodular cost function defined on subsets of edges. That means, the cost of an edge that is added to the current cut set C depends on the edges in C. This generalization of the cost in the standard min-cut problem immediately makes the problem harder. Not only do we prove NP hardness even for nonnegative submodular costs, but also show a lower bound of Ω(|V |1/3) on the approximation factor for the problem. On the positive side, we propose and compare four approximation algorithms with an overall approximation factor of min {|V |/2, |C∗|, O(√|E | log |V |), |Pmax|}, where C ∗ is the optimal solution, and Pmax is the longest s, t path across the cut between given s, t. The algorithms and additionally suggested heuristics appear to do well in practice. 1