June 26, 2019, 4:20 PM - 5:00 PM
96 Frelinghuysen Road
Piscataway, NJ 08854
Click here for map.
Yuehaw Khoo, Stanford University
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.