Special Talk: Topology, Geometry and Data Seminar - Soledad Villar

Image
Soledad Villar
September 25, 2017
4:00PM - 5:00PM
Location
Cockins Hall 240

Date Range
Add to Calendar 2017-09-25 16:00:00 2017-09-25 17:00:00 Special Talk: Topology, Geometry and Data Seminar - Soledad Villar Title: Quadratic assignment on different data modelsSpeaker: Soledad Villar (New York University)Abstract: 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.Seminar URL: https://research.math.osu.edu/tgda/tgda-seminar.html Cockins Hall 240 Department of Mathematics math@osu.edu America/New_York public
Description

Title: Quadratic assignment on different data models

SpeakerSoledad Villar (New York University)

Abstract: 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.

Seminar URLhttps://research.math.osu.edu/tgda/tgda-seminar.html

Events Filters: