Notes on Graph Cuts with Submodular Edge Weights

Jegelka, S; Bilmes, J

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

会議論文

Notes on Graph Cuts with Submodular Edge Weights

MPS-Authors

/persons/resource/persons83994

Jegelka, S
Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society;
Max Planck Institute for Biological Cybernetics, Max Planck Society;

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

NIPS-Workshop-2009-Jegelka.pdf
(全文テキスト（全般）), 102KB

付随資料 (公開)

There is no public supplementary material available

引用

Jegelka, S., & Bilmes, J. (2009). Notes on Graph Cuts with Submodular Edge Weights. In NIPS 2009 Workshop on Discrete Optimization in Machine Learning: Submodularity, Sparsity & Polyhedra (DISCML) (pp. 1-6).

引用: https://hdl.handle.net/11858/00-001M-0000-0013-C1DE-D

要旨

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.