2017/11/29 by Florian Bernard, Christian Theobalt, Bernard, Florian +3 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computer Vision and Pattern Recognition (cs.CV) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1711.10733
openalex publication_date 2017/11/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this work we study convex relaxations of quadratic optimisation problems over permutation matrices. While existing semidefinite programming approaches can achieve remarkably tight relaxations, they have the strong disadvantage that they lift the original n × n-dimensional variable to an n2 × n2-dimensional variable, which limits their practical applicability. In contrast, here we present a lifting-free convex relaxation that is provably at least as tight as existing (lifting-free) convex relaxations. We demonstrate experimentally that our approach is superior to existing convex and non-convex methods for various problems, including image arrangement and multi-graph matching.