Cooperative Cuts: Graph Cuts with Submodular Edge Weights
Lists
Only you see this
Abstract
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
BibTeX
@inproceedings{jegelka2010cooperative,
author = {Stefanie Jegelka and Jeffrey A. Bilmes},
title = {{Cooperative Cuts: Graph Cuts with Submodular Edge Weights}},
booktitle = {MPG.PuRe},
year = {2010},
}Loading related content...