@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},
  author = {Jegelka, S. and Bilmes, J.},
  month_numeric = {12}
}