Theory Seminar, Wednesday Dec 17: Shinwoo An (BIU) - Dimension Reduction for Clustering: The Curious Case of Discrete Centers

[Arnold Filtser]

Hi all,

Next week (Wed Dec 17, at 12) we will meet for our theory seminar.

Location: Building 503 room 226.

The speaker will be our very own  Shinwoo An.

Looking forward to seeing you all there,

Arnold

https://theory.cs.biu.ac.il/

Speaker: Shinwoo An (BIU)
Title:  Approximation Algorithm for the Geometric Multimatching Problem
Abstract: Let $S, T$ be two sets of points in a metric space with total size $n$, and each point of $S\cup T$ has a demand value that specifies a lower bound on the number of points it must be matched with from the other set. A multimatching between $S\cup T$ is a way of computing a collection of pairs between points in $S$ and $T$, such that the number of times each point is matched satisfies its demands. The geometric multimatching problem seeks to find a multimatching of minimum total cost, where the cost is defined as the sum of distances between matched pairs.

We present the first non-trivial result for this problem when the underlying metric space has a bounded doubling dimension. Specifically, we provide the first near-linear-time approximation scheme for this problem in terms of the output size. As a byproduct, we improve upon the best-known approximation algorithm for the geometric many-to-many matching problem, previously introduced by Bandyapadhyay and Xue (SoCG'24), which won the best paper award at SoCG'24.

This is a joint work with Eunjin Oh and Jie Xue.

[Arnold Filtser]

The seminar starts in one hour!