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.