Quadratic Assignment on Different Data Models
Episode details
Episode description
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. See more at https://www.microsoft.com/en-us/research/video/quadratic-assignment-on-different-data-models/
Watch also from the same channel
More episodes from this channel
You might be interested in
