Header logo is

Notes on Graph Cuts with Submodular Edge Weights


Conference Paper


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

Department(s): Empirical Inference
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

Links: PDF


  title = {Notes on Graph Cuts with Submodular Edge Weights},
  author = {Jegelka, S. and Bilmes, J.},
  pages = {1-6},
  month = dec,
  year = {2009},
  month_numeric = {12}