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}
}