• Login
    View Item 
    •   Eurographics DL Home
    • Eurographics Partner Events
    • VMV: Vision, Modeling, and Visualization
    • VMV17
    • View Item
    •   Eurographics DL Home
    • Eurographics Partner Events
    • VMV: Vision, Modeling, and Visualization
    • VMV17
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Efficient Lifted Relaxations of the Quadratic Assignment Problem

    Thumbnail
    View/Open
    119-128.pdf (890.7Kb)
    Date
    2017
    Author
    Burghard, Oliver
    Klein, Reinhard
    Pay-Per-View via TIB Hannover:

    Try if this item/paper is available.

    Metadata
    Show full item record
    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.
    BibTeX
    @inproceedings {vmv.20171267,
    booktitle = {Vision, Modeling & Visualization},
    editor = {Matthias Hullin and Reinhard Klein and Thomas Schultz and Angela Yao},
    title = {{Efficient Lifted Relaxations of the Quadratic Assignment Problem}},
    author = {Burghard, Oliver and Klein, Reinhard},
    year = {2017},
    publisher = {The Eurographics Association},
    ISBN = {978-3-03868-049-9},
    DOI = {10.2312/vmv.20171267}
    }
    URI
    http://dx.doi.org/10.2312/vmv.20171267
    https://diglib.eg.org:443/handle/10.2312/vmv20171267
    Collections
    • VMV17

    Eurographics Association copyright © 2013 - 2020 
    Send Feedback | Contact - Imprint | Data Privacy Policy | Disable Google Analytics
    Theme by @mire NV
    System hosted at  Graz University of Technology.
    TUGFhA
     

     

    Browse

    All of Eurographics DLCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    BibTeX | TOC

    Create BibTeX Create Table of Contents

    Eurographics Association copyright © 2013 - 2020 
    Send Feedback | Contact - Imprint | Data Privacy Policy | Disable Google Analytics
    Theme by @mire NV
    System hosted at  Graz University of Technology.
    TUGFhA