A dual ascent framework for Lagrangean decomposition of combinatorial problems
Swoboda P, Kuske J, Savchynskyy B. 2017. A dual ascent framework for Lagrangean decomposition of combinatorial problems. CVPR: Computer Vision and Pattern Recognition vol. 2017, 4950–4960.
Download
Conference Paper
| Published
| English
Scopus indexed
Author
Swoboda, PaulISTA;
Kuske, Jan;
Savchynskyy, Bogdan
Department
Abstract
We propose a general dual ascent framework for Lagrangean decomposition of combinatorial problems. Although methods of this type have shown their efficiency for a number of problems, so far there was no general algorithm applicable to multiple problem types. In this work, we propose such a general algorithm. It depends on several parameters, which can be used to optimize its performance in each particular setting. We demonstrate efficacy of our method on graph matching and multicut problems, where it outperforms state-of-the-art solvers including those based on subgradient optimization and off-the-shelf linear programming solvers.
Publishing Year
Date Published
2017-07-01
Publisher
IEEE
Volume
2017
Page
4950-4960
Conference
CVPR: Computer Vision and Pattern Recognition
Conference Location
Honolulu, HA, United States
Conference Date
2017-07-21 – 2017-07-26
ISBN
IST-REx-ID
Cite this
Swoboda P, Kuske J, Savchynskyy B. A dual ascent framework for Lagrangean decomposition of combinatorial problems. In: Vol 2017. IEEE; 2017:4950-4960. doi:10.1109/CVPR.2017.526
Swoboda, P., Kuske, J., & Savchynskyy, B. (2017). A dual ascent framework for Lagrangean decomposition of combinatorial problems (Vol. 2017, pp. 4950–4960). Presented at the CVPR: Computer Vision and Pattern Recognition, Honolulu, HA, United States: IEEE. https://doi.org/10.1109/CVPR.2017.526
Swoboda, Paul, Jan Kuske, and Bogdan Savchynskyy. “A Dual Ascent Framework for Lagrangean Decomposition of Combinatorial Problems,” 2017:4950–60. IEEE, 2017. https://doi.org/10.1109/CVPR.2017.526.
P. Swoboda, J. Kuske, and B. Savchynskyy, “A dual ascent framework for Lagrangean decomposition of combinatorial problems,” presented at the CVPR: Computer Vision and Pattern Recognition, Honolulu, HA, United States, 2017, vol. 2017, pp. 4950–4960.
Swoboda P, Kuske J, Savchynskyy B. 2017. A dual ascent framework for Lagrangean decomposition of combinatorial problems. CVPR: Computer Vision and Pattern Recognition vol. 2017, 4950–4960.
Swoboda, Paul, et al. A Dual Ascent Framework for Lagrangean Decomposition of Combinatorial Problems. Vol. 2017, IEEE, 2017, pp. 4950–60, doi:10.1109/CVPR.2017.526.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
File Name
2017_CVPR_Swoboda.pdf
898.65 KB
Access Level
Open Access
Date Uploaded
2019-01-18
MD5 Checksum
72fd291046bd8e5717961bd68f6b6f03
Export
Marked PublicationsOpen Data ISTA Research Explorer