A dual ascent framework for Lagrangean decomposition of combinatorial problems Conference Paper


Author(s): Swoboda, Paul; Kuske, Jan; Savchynskyy, Bogdan
Title: A dual ascent framework for Lagrangean decomposition of combinatorial problems
Affiliation IST Austria
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.
Conference Title: CVPR: Computer Vision and Pattern Recognition
Conference Dates: July 22 - 25, 2017
Conference Location: Honolulu, Hawaii, USA
Publisher: IEEE  
Date Published: 2017-07-01
Start Page: 1596
End Page: 1606
URL:
DOI: 10.1109/CVPR.2017.526
Notes: The authors would like to thank Vladimir Kolmogorov for helpful discussions. The first authors was supported by the European Research Council under the European Unions Sev- enth Framework Programme (FP7/2007-2013)/ERC grant agreement no 616160, the second author by DFG Grant GRK 1653 and the last author by the European Research Council under the European Unions Horizon 2020 research and innovation programme (grant agreement No 647769) and the DFG Grant ”ERBI” SA 2640/1-1.
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work