论文标题
$ \ tilde {o}（n^{5/4}）$ time $ \ varepsilon $ -appRoximation算法RMS在飞机上匹配的RMS
An $\tilde{O}(n^{5/4})$ Time $\varepsilon$-Approximation Algorithm for RMS Matching in a Plane
论文作者
论文摘要
2-Wasserstein距离（或RMS距离）是在机器学习中具有令人兴奋的应用程序之间相似性的有用度量。对于离散的分布，可以通过在由两个点$ a，b \ subset \ mathbb {r}^2 $的两个多组给出的完整的两部分图上找到最低成本的完美匹配来表示，可以表达出该距离的问题。尽管对于地面距离为欧几里得人（Sharathkumar和Agarwal，Jacm 2020）的情况下，有一个接近线性的时间相对$ \ varepsilon $ - approximation算法，所有现有的相对$ \ varepsilon $ - approximation $ -Approximation $ -RMS距离rms距离rms距离rms the rms距这主要是因为与欧几里得距离不同，平方的欧几里得距离不是公制。在本文中，对于RMS距离，我们提出了一种新的$ \ VAREPSILON $ -APPROXIMATION算法，该算法以$ O（N^{5/4} \ Mathrm {Poly} \ {poly} \ {\ log n，1/\ varepsilon \}）$时间运行。 我们的算法的灵感来自最近在两部分平面图中找到最低成本完美匹配的方法（Asathulla等，Talg 2020）。它们的算法在很大程度上取决于亚线性大小的顶点分离器以及需要平面性的最短路径数据结构。令人惊讶的是，我们能够为完整的几何图设计类似的算法，该算法远非平面并且没有任何顶点分离器。我们算法的中央组件包括一个基于Quadtree的距离，该距离近似于平方的欧几里得距离和一个支持匈牙利搜索和以下时间增强的数据结构。
The 2-Wasserstein distance (or RMS distance) is a useful measure of similarity between probability distributions that has exciting applications in machine learning. For discrete distributions, the problem of computing this distance can be expressed in terms of finding a minimum-cost perfect matching on a complete bipartite graph given by two multisets of points $A,B \subset \mathbb{R}^2$, with $|A|=|B|=n$, where the ground distance between any two points is the squared Euclidean distance between them. Although there is a near-linear time relative $\varepsilon$-approximation algorithm for the case where the ground distance is Euclidean (Sharathkumar and Agarwal, JACM 2020), all existing relative $\varepsilon$-approximation algorithms for the RMS distance take $Ω(n^{3/2})$ time. This is primarily because, unlike Euclidean distance, squared Euclidean distance is not a metric. In this paper, for the RMS distance, we present a new $\varepsilon$-approximation algorithm that runs in $O(n^{5/4}\mathrm{poly}\{\log n,1/\varepsilon\})$ time. Our algorithm is inspired by a recent approach for finding a minimum-cost perfect matching in bipartite planar graphs (Asathulla et al., TALG 2020). Their algorithm depends heavily on the existence of sub-linear sized vertex separators as well as shortest path data structures that require planarity. Surprisingly, we are able to design a similar algorithm for a complete geometric graph that is far from planar and does not have any vertex separators. Central components of our algorithm include a quadtree-based distance that approximates the squared Euclidean distance and a data structure that supports both Hungarian search and augmentation in sub-linear time.
