Header logo is

Cooperative Cuts: Graph Cuts with Submodular Edge Weights

2010

Talk

ei


We introduce cooperative cut, a minimum cut problem whose cost is a submodular function on sets of edges: the cost of an edge that is added to a cut set depends on the edges in the set. Applications are e.g. in probabilistic graphical models and image processing. We prove NP hardness and a polynomial lower bound on the approximation factor, and upper bounds via four approximation algorithms based on different techniques. Our additional heuristics have attractive practical properties, e.g., to rely only on standard min-cut. Both our algorithms and heuristics appear to do well in practice.

Author(s): Jegelka, S. and Bilmes, J.
Year: 2010
Month: July
Day: 0

Department(s): Empirical Inference
Bibtex Type: Talk (talk)

Digital: 0
Event Name: 24th European Conference on Operational Research (EURO XXIV)
Event Place: Lisboa, Portugal

Links: PDF
Web

BibTex

@talk{JegelkaB2010_2,
  title = {Cooperative Cuts: Graph Cuts with Submodular Edge Weights},
  author = {Jegelka, S. and Bilmes, J.},
  month = jul,
  year = {2010},
  month_numeric = {7}
}