---
_id: '915'
abstract:
- lang: eng
  text: We propose a dual decomposition and linear program relaxation of the NP-hard
    minimum cost multicut problem. Unlike other polyhedral relaxations of the multicut
    polytope, it is amenable to efficient optimization by message passing. Like other
    polyhedral relaxations, it can be tightened efficiently by cutting planes.  We
    define an algorithm that alternates between message passing and efficient separation
    of cycle- and odd-wheel inequalities. This algorithm is more efficient than state-of-the-art
    algorithms based on linear programming, including algorithms written in the framework
    of leading commercial software, as we show in experiments with large instances
    of the problem from applications in computer vision, biomedical image analysis
    and data mining.
article_processing_charge: No
author:
- first_name: Paul
  full_name: Swoboda, Paul
  id: 446560C6-F248-11E8-B48F-1D18A9856A87
  last_name: Swoboda
- first_name: Bjoern
  full_name: Andres, Bjoern
  last_name: Andres
citation:
  ama: 'Swoboda P, Andres B. A message passing algorithm for the minimum cost multicut
    problem. In: Vol 2017. IEEE; 2017:4990-4999. doi:<a href="https://doi.org/10.1109/CVPR.2017.530">10.1109/CVPR.2017.530</a>'
  apa: 'Swoboda, P., &#38; Andres, B. (2017). A message passing algorithm for the
    minimum cost multicut problem (Vol. 2017, pp. 4990–4999). Presented at the CVPR:
    Computer Vision and Pattern Recognition, Honolulu, HA, United States: IEEE. <a
    href="https://doi.org/10.1109/CVPR.2017.530">https://doi.org/10.1109/CVPR.2017.530</a>'
  chicago: Swoboda, Paul, and Bjoern Andres. “A Message Passing Algorithm for the
    Minimum Cost Multicut Problem,” 2017:4990–99. IEEE, 2017. <a href="https://doi.org/10.1109/CVPR.2017.530">https://doi.org/10.1109/CVPR.2017.530</a>.
  ieee: 'P. Swoboda and B. Andres, “A message passing algorithm for the minimum cost
    multicut problem,” presented at the CVPR: Computer Vision and Pattern Recognition,
    Honolulu, HA, United States, 2017, vol. 2017, pp. 4990–4999.'
  ista: 'Swoboda P, Andres B. 2017. A message passing algorithm for the minimum cost
    multicut problem. CVPR: Computer Vision and Pattern Recognition vol. 2017, 4990–4999.'
  mla: Swoboda, Paul, and Bjoern Andres. <i>A Message Passing Algorithm for the Minimum
    Cost Multicut Problem</i>. Vol. 2017, IEEE, 2017, pp. 4990–99, doi:<a href="https://doi.org/10.1109/CVPR.2017.530">10.1109/CVPR.2017.530</a>.
  short: P. Swoboda, B. Andres, in:, IEEE, 2017, pp. 4990–4999.
conference:
  end_date: 2017-07-26
  location: Honolulu, HA, United States
  name: 'CVPR: Computer Vision and Pattern Recognition'
  start_date: 2017-07-21
corr_author: '1'
date_created: 2018-12-11T11:49:11Z
date_published: 2017-07-01T00:00:00Z
date_updated: 2024-11-04T13:52:34Z
day: '01'
ddc:
- '000'
department:
- _id: VlKo
doi: 10.1109/CVPR.2017.530
ec_funded: 1
external_id:
  isi:
  - '000418371405009'
file:
- access_level: open_access
  checksum: 7e51dacefa693574581a32da3eff63dc
  content_type: application/pdf
  creator: dernst
  date_created: 2019-01-18T12:52:46Z
  date_updated: 2020-07-14T12:48:15Z
  file_id: '5849'
  file_name: Swoboda_A_Message_Passing_CVPR_2017_paper.pdf
  file_size: 883264
  relation: main_file
file_date_updated: 2020-07-14T12:48:15Z
has_accepted_license: '1'
intvolume: '      2017'
isi: 1
language:
- iso: eng
month: '07'
oa: 1
oa_version: Submitted Version
page: 4990-4999
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '616160'
  name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication_identifier:
  isbn:
  - 978-153860457-1
publication_status: published
publisher: IEEE
publist_id: '6526'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A message passing algorithm for the minimum cost multicut problem
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 2017
year: '2017'
...