Geometry Seminar

---

Efficient Approximation Algorithms for Geometric Many-to-Many Matching

Speaker: Jie Xue, NYU Shanghai

Location: Warren Weaver Hall 1314 in person and on Zoom

Videoconference link: https://youtu.be/I-DY9e4PqOo

Date: Tuesday, April 29, 2025, 6 p.m.

Synopsis:

Geometric matching is an important topic in computational geometry and has been extensively studied over decades. In this talk, we shall discuss the geometric many-to-many matching problem, where we are given a set of n colored points in a Euclidean space and the goal is to compute a set of edges between pairs of points with different colors such that (i) each point is incident to at least one edge and (ii) the total length of the edges is minimized. We shall present several recent developments on geometric many-to-many matching, which gave near-linear time approximation schemes for the problem.

Notes:

In person and simultaneously Zoom-broadcast at the usual place; sent via the mailing list.  Contact Boris Aronov to be put on the mailing list and/or get access to the physical location if you are not NYU-affiliated.