Clique-based semidefinite relaxation of the quadratic assignment problem

Thu, Nov 3, 2016, 2:30 pm

The matching problem between two adjacency matrices, A and B, can be formulated as the NP-hard quadratic assignment problem (QAP). While the QAP admits a semidefinite (SDP) relaxation that is often tight in practice, this SDP scales badly as it involves a matrix variable of size n^2 by n^2. To achieve a speed up, a further relaxation of the SDP will be described, where the number of variables scale as O(bn^2), where b is the number of non-zero entries in B. The dual problem of this relaxation has a natural three-block structure that can be solved via Alternating Direction Method of Multipliers (ADMM) in a distributed manner. I will show results that suggest this relaxation offers a good compromise between speed and tightness in practice, and will discuss how the assignment problem in Nuclear Magnetic Resonance Spectroscopy can be formulated as a QAP with sparse B.

This is joint work with Yuehaw Khoo and Amit Singer.

101A McDonnell Hall
Event category: 

Upcoming Events

Prof. Afonso Bandeira, ETH Zurich

Mon, Sep 11, 2023, 4:30 pm
Location: 214 Fine Hall

Prof. Jonathan Pillow, Princeton University

Mon, Sep 18, 2023, 4:30 pm
Location: 214 Fine Hall

No PACM Colloquium scheduled on this day-Yom Kippur

Mon, Sep 25, 2023, 4:30 pm
Location: 214 Fine Hall