Yuehaw Khoo, Stanford University

Abstract

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 semide nite (SDP) relaxation that is often tight in practice, this SDP scales badly as it involves a matrix variable of size n2 by n2. To achieve a speed up, a further relaxation of the SDP will be described, where the number of variables scale as O(bn2), 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 o ers 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 Jose Simoes Bravo Ferreira and Amit Singer.

Video