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