A study of Lagrangean decompositions and dual ascent solvers for graph matching

Tools

Item Type:	Conference or Workshop Item
Title:	A study of Lagrangean decompositions and dual ascent solvers for graph matching
Creators Name:	Swoboda, P., Rother, C., Alhaija, H.A., Kainmüller, D. and Savchynskyy, B.
Abstract:	We study the quadratic assignment problem, in computer vision also known as graph matching. Two leading solvers for this problem optimize the Lagrange decomposition duals with sub-gradient and dual ascent (also known as message passing) updates. We explore this direction further and propose several additional Lagrangean relaxations of the graph matching problem along with corresponding algorithms, which are all based on a common dual ascent framework. Our extensive empirical evaluation gives several theoretical insights and suggests a new state-of-the-art anytime solver for the considered problem. Our improvement over state-of-the-art is particularly visible on a new dataset with large-scale sparse problem instances containing more than 500 graph nodes each.
Keywords:	Combinatorial Optimization, Message Passing, Pattern Matching, Empirical Evaluations, Graph Matching Problems, Graph Matchings, Lagrange, Lagrangean Relaxation, Problem Instances, Quadratic Assignment Problems, State of the Art, Computer Vision
Title of Book:	2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
Page Range:	7062-7071
Date:	9 November 2017
Official Publication:	https://doi.org/10.1109/CVPR.2017.747

Repository Staff Only: item control page