A dual ascent framework for Lagrangean decomposition of combinatorial problems

P. Swoboda, J. Kuske, B. Savchynskyy, in:, IEEE, 2017, pp. 4950–4960.

Download
OA 898.65 KB

Conference Paper | Published | English
Author
; ;
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
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
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.
Main File(s)
File Name
Access Level
OA Open Access
Last Uploaded
2019-01-18T12:45:55Z


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar
ISBN Search