English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Cooperative Cuts: Graph Cuts with Submodular Edge Weights

Jegelka, S., & Bilmes, J. (2010). Cooperative Cuts: Graph Cuts with Submodular Edge Weights. In 24th European Conference on Operational Research (EURO XXIV) (pp. 171).

Item is

Files

show Files

Locators

show
hide
Description:
-
OA-Status:

Creators

show
hide
 Creators:
Jegelka, S1, 2, Author           
Bilmes, J1, 2, Author           
Affiliations:
1Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society, ou_1497795              
2Max Planck Institute for Biological Cybernetics, Max Planck Society, Spemannstrasse 38, 72076 Tübingen, DE, ou_1497794              

Content

show
hide
Free keywords: -
 Abstract: We introduce cooperative cut, a minimum cut problem whose cost is a submodular function on sets of edges: the cost of an edge that is added to a cut set depends on the edges in the set. Applications are e.g. in probabilistic graphical
models and image processing. We prove NP hardness and a polynomial lower bound on the approximation factor, and upper bounds via four approximation algorithms based on different techniques. Our additional heuristics have attractive practical properties, e.g., to rely only on standard min-cut. Both our algorithms and heuristics appear to do well in practice.

Details

show
hide
Language(s):
 Dates: 2010-07
 Publication Status: Published in print
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: BibTex Citekey: JegelkaB2010_2
 Degree: -

Event

show
hide
Title: 24th European Conference on Operational Research (EURO XXIV)
Place of Event: Lisboa, Portugal
Start-/End Date: 2010-07-11 - 2010-07-14

Legal Case

show

Project information

show

Source 1

show
hide
Title: 24th European Conference on Operational Research (EURO XXIV)
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 171 Identifier: -