Notes on Graph Cuts with Submodular Edge Weights
2009
Conference Paper
ei
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
Web |
BibTex @inproceedings{JegelkaB2009, title = {Notes on Graph Cuts with Submodular Edge Weights}, author = {Jegelka, S. and Bilmes, J.}, pages = {1-6}, month = dec, year = {2009}, doi = {}, month_numeric = {12} } |