Efficient Lifted Relaxations of the Quadratic Assignment Problem

In proceedings of Vision, Modeling & Visualization (VMV), 2017
 

Abstract

Quadratic assignment problems (QAPs) and quadratic assignment matchings (QAMs) recently gained a lot of interest in computer graphics and vision, e.g. for shape and graph matching. Literature describes several convex relaxations to approximate solutions of the NP-hard QAPs in polynomial time. We compare the convex relaxations recently introduced in computer graphics and vision to established approaches in discrete optimization. Building upon a unified constraint formulation we theoretically analyze their solution spaces and their approximation quality. Experiments on a standard benchmark as well as on instances of the shape matching problems support our analysis. It turns out that often the bounds of a tight linear relaxation are competitive with the bounds of semidefinite programming (SDP) relaxations, while the linear relaxation is often much faster to calculate. Indeed, for many instances the bounds of the linear relaxation are only slightly worse than the SDP relaxation of Zhao [ZKRW98, PR09], which itself is at least as accurate as the relaxations currently used in computer graphics and vision. Solving the SDP relaxations can often be accelerated considerably from hours to minutes using the recently introduced approximation method for trace bound SDPs [WSvdHT16], but nonetheless calculating linear relaxations is faster in most cases. For the shape matching problem all relaxations generate the optimal solution, only that the linear relaxation does so faster. Our results generalize as well to QAMs for which we deliver new relaxations. Furthermore by interpreting the Product Manifold Filter [VLR 17] in the context of QAPs we show how to automatically calculate correspondences between shapes of several hundred points.

Bilder

Paper herunterladen

Paper herunterladen

Bibtex

@INPROCEEDINGS{BK17:QAP,
     author = {Burghard, Oliver and Klein, Reinhard},
      title = {Efficient Lifted Relaxations of the Quadratic Assignment Problem},
  booktitle = {Vision, Modeling {\&} Visualization (VMV)},
       year = {2017},
   abstract = {Quadratic assignment problems (QAPs) and quadratic assignment matchings (QAMs) recently gained a lot
               of interest in computer graphics and vision, e.g. for shape and graph matching. Literature describes
               several convex relaxations to approximate solutions of the NP-hard QAPs in polynomial time. We
               compare the convex relaxations recently introduced in computer graphics and vision to established
               approaches in discrete optimization. Building upon a unified constraint formulation we theoretically
               analyze their solution spaces and their approximation quality. Experiments on a standard benchmark
               as well as on instances of the shape matching problems support our analysis. It turns out that often
               the bounds of a tight linear relaxation are competitive with the bounds of semidefinite programming
               (SDP) relaxations, while the linear relaxation is often much faster to calculate. Indeed, for many
               instances the bounds of the linear relaxation are only slightly worse than the SDP relaxation of
               Zhao [ZKRW98, PR09], which itself is at least as accurate as the relaxations currently used in
               computer graphics and vision. Solving the SDP relaxations can often be accelerated considerably from
               hours to minutes using the recently introduced approximation method for trace bound SDPs [WSvdHT16],
               but nonetheless calculating linear relaxations is faster in most cases. For the shape matching
               problem all relaxations generate the optimal solution, only that the linear relaxation does so
               faster. Our results generalize as well to QAMs for which we deliver new relaxations. Furthermore by
               interpreting the Product Manifold Filter [VLR 17] in the context of QAPs we show how to
               automatically calculate correspondences between shapes of several hundred points.}
}