Quadratic Assignment on Different Data Models

Tuesday, September 19, 2017 - 1:25pm - 2:25pm
Lind 305
Soledad Villar (New York University)
Quadratic assignment is a very general problem in theoretical computer science. It includes graph matching, the traveling salesman problem, and the Gromov-Hausdorff distance between finite metric spaces as particular cases. Quadratic assignment is in general NP-hard and even hard to approximate, but in fact the problem can be tractable for a large subset of instances. In this talk we present different algorithmic approaches that lead to meaningful results for different data models. A semidefinite relaxation provides a pseudometric that can be computed in polynomial-time and has similar topological properties to the GH distance. A projected power iteration algorithm succeeds at aligning noisy networks. And a graph neural network can actually learn an algorithm to solve network alignment and the traveling salesman problem from solved problem instances.

Soledad Villar is a Moore-Sloan Research Fellow at the Center for Data Science in New York University. She did her PhD in Mathematics at the University of Texas at Austin advised by Rachel Ward. Before that she completed her undergraduate studies in her home country, Uruguay. Her research is related to optimization, statistics, machine learning, and applied harmonic analysis. She is also interested in data-related problems from a geometric, topologic and algorithmic point of view.