Institute Homepage DE Sign In

Back

Empirical Inference Conference Paper 2009

Notes on Graph Cuts with Submodular Edge Weights

no image
Empirical Inference
Stefanie Jegelka
no image
Empirical Inference
Jeff Bilmes

Generalizing the cost in the standard min-cut problem to a submodular cost function 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 (s, t) cut version of the problem. On the positive side, we propose and compare three approximation algorithms with an overall approximation factor of O(min{|V |,p|E| log |V |}) that appear to do well in practice.

Author(s): Jegelka, S. and Bilmes, J.
Pages: 1-6
Year: 2009
Month: December
Day: 0
Bibtex Type: Conference Paper (inproceedings)
Event Name: NIPS 2009 Workshop on Discrete Optimization in Machine Learning: Submodularity, Sparsity & Polyhedra (DISCML)
Event Place: Whistler, BC, Canada
Digital: 0
Electronic Archiving: grant_archive
Links:

BibTex 

@inproceedings{JegelkaB2009,
  title = {Notes on Graph Cuts with Submodular Edge Weights},
  abstract = {Generalizing the cost in the standard min-cut problem to a submodular cost function 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 (s, t) cut version of the problem. On the positive side, we propose and compare three approximation algorithms with an overall approximation factor of O(min{|V |,p|E| log |V |}) that appear to do well in practice.},
  pages = {1-6},
  month = dec,
  year = {2009},
  slug = {jegelkab2009},
  author = {Jegelka, S. and Bilmes, J.},
  month_numeric = {12}
}