A message passing algorithm for the minimum cost multicut problem

P. Swoboda, B. Andres, in:, IEEE, 2017, pp. 4990–4999.

Download
OA Swoboda_A_Message_Passing_CVPR_2017_paper.pdf 883.26 KB

Conference Paper | Published | English

Scopus indexed
Author
Swoboda, PaulIST Austria; Andres, Bjoern
Department
Abstract
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.
Publishing Year
Date Published
2017-07-01
Volume
2017
Page
4990-4999
Conference
CVPR: Computer Vision and Pattern Recognition
Conference Location
Honolulu, HA, United States
Conference Date
2017-07-21 – 2017-07-26
IST-REx-ID
915

Cite this

Swoboda P, Andres B. A message passing algorithm for the minimum cost multicut problem. In: Vol 2017. IEEE; 2017:4990-4999. doi:10.1109/CVPR.2017.530
Swoboda, P., & 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. https://doi.org/10.1109/CVPR.2017.530
Swoboda, Paul, and Bjoern Andres. “A Message Passing Algorithm for the Minimum Cost Multicut Problem,” 2017:4990–99. IEEE, 2017. https://doi.org/10.1109/CVPR.2017.530.
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.
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.
Swoboda, Paul, and Bjoern Andres. A Message Passing Algorithm for the Minimum Cost Multicut Problem. Vol. 2017, IEEE, 2017, pp. 4990–99, doi:10.1109/CVPR.2017.530.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
Access Level
OA Open Access
Date Uploaded
2019-01-18
MD5 Checksum
7e51dacefa693574581a32da3eff63dc


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar
ISBN Search