Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time

We would like to thank the reviewer for their time and for providing valuable comments.

• “The texts in Figures 2 and 3 are generally very small. My suggestion would be to have the same figures with better resolutions in the appendix and add a pointer.”

All figures will be replicated in the appendix, allowing for a more readable presentation.

• “Do you have any opinion on how tight your result is? Is it possible to, say, get any approximation in $\text{polylog } n$ update time?”

For a choice $\varepsilon = 1/ \log n$, our algorithm reports an $O(\log n)$-approximation solution in $O(\text{polylog } n)$ update time. We believe that there are instances where our current algorithms attain the claimed trade-off between approximation ratio and update time. It’s an interesting open question whether such a trade-off can be improved, and will likely require new ideas.

We would like to thank the reviewer for their time and for providing valuable comments. For the minor comments and typos not addressed below, we will incorporate them in the next version of the paper.

• “Missing the impact statement.”

We will include the following impact statement, and we apologize for our oversight:

This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.

• “In your experimental results, you used $p=2,8,32$, but your paper mentions the value $p$ as $n^{−\varepsilon}$, which is less than $1$. I assume that the diameter of the space plays a role in the choice of $p$ in your experiments, but I could not get a sense of what is in fact the value of $\varepsilon$.”

To clarify, we choose the value of $p$ as $n^\varepsilon$ in the paper and obtain an approximation ratio of $O(1/\varepsilon)$. Here are some examples to give a sense of the scale of $\varepsilon$:

• our largest experiment had $n=1 000 000$ and $p=2$ corresponding to $\varepsilon \approx 1/20$,

• our uniform synthetic data set where points were integers between $0$ and $500$, the choice of $p=32$ corresponds to $\varepsilon \approx 0.55$.

Empirically, all choices of $p$ achieve a significantly better approximation ratio in practice than our worst-case theoretical guarantee (see Figure 5 in Appendix G).

We would like to thank the reviewer for their time and for providing valuable comments.

• "The contribution is not clear enough in relation to [Xu-Ding 2024]."

The Xu-Ding paper studies a slightly different problem: dynamic maintenance of optimal transport. Specifically, the goal is to design a data structure that accelerates executing 'one iteration' of the Network Simplex Algorithm on an explicit complete bi-partite graph in $O(n)$ time, where $n$ is the current number of points. Their work is concerned with maintaining an exact solution, within numeric computing accuracy, after the insertion/deletion of a vertex to the min-cost flow problem. Since their algorithm operates on a complete, bipartite graph, it requires $\Omega(n^2)$ space to store the edge weights and $\Omega(n)$ update time to insert a new vertex. Moreover, in the worst case, the update time can take up to $O(n^2)$ time. As such, the algorithm and the implementation cannot handle very large instances in practice.

In contrast, our paper studies the problem of quickly maintaining an approximate solution to the Euclidean bi-chromatic bipartite matching (i.e., optimal transport with uniform demands), in time that is sub-linear in $n$. For example, taking $\varepsilon = 1/2$ gives an update time of $O(\sqrt{n})$ for updating an $O(1)$-approximate matching. Our proposed tree structure uses $O(n)$ space, regardless of $\varepsilon$, which makes the approach practical for very large inputs. Moreover, our lower-bound in Thm. F.1 shows that the approximation ratio must be at least $2$ for any dynamic algorithm to achieve a sublinear update time.

In the related works section, our focus has been to compare our contributions with the known approximation algorithms that run in near-linear time and space, as those are also applicable to larger instances. That being said, as per the reviewer’s suggestion, we will include the above comparison to the Xu-Ding work in the next version of the paper.

Experimental comparison with [Xu-Ding 2024]

We ran the code of [Xu-Ding 2024] on our benchmark dataset (Unif-Vs-Gaussian). We have observed that the insertion time slowed down substantially after inserting $1$k point-pairs (source and sink). In fact, already inserting $5$k point-pairs took more than $12$GB RAM and longer than $3$ hours in total, which is when we had to terminate the process as it was running out of memory. Note that this is already $>1$s per update on a small instance.

In contrast, our experimental results show that the update time of our proposed algorithm remains $<1$ms for very large instances (up to $n=10^6$ in Figure $2$; right), with the quality of the solution being within a factor of two from the optimum (see Figure $5$; right).

We would like to thank the reviewer for their time and for providing valuable comments.

• “Do the authors have an estimate for the constant in the $O(1/ \varepsilon)$ approximation. I understand that asymptotically it doesn’t matter but it would be nice to understand what the factor is for say $\sqrt{n}$ update time.”

We haven’t done an exact analysis of the constant in the $O(1/ \varepsilon)$ approximation guarantee. However, if one would want to achieve $O(\sqrt{n})$ update time, we expect the approximation ratio to be $< 20$.

• “Does the analysis work for weighted matchings e.g. something like optimal transport? Of course one can replicate the points by their weight but it leads to some blowup in the parameters.”

This is a great question. We believe it works and our algorithm should extend to this setting, but details need to be worked out.

• “The case of $\varepsilon \approx 1/ \log⁡(n)$ seems especially interesting since one gets $O(\log ⁡n)$ update time. Is there any hopes of improving the running time in this regime?”

This is a natural question to consider, but we’re not aware of any techniques of pushing down the runtime to something sub-logarithmic.

• “Can the authors quickly survey what is known about the dynamic problem in high dimensional settings? i.e. when $d$ is not constant? What is the dependency on $d$ of the current algorithms? Does an exponential factor in $d$ show up in the approximation or in the update time?”

To the best of our knowledge, the dynamic version of our problem in higher dimensions hasn’t been studied yet. However, we can easily extend our algorithm to work in any dimension $d$. The best possible trade-offs need to be worked out, but we believe that our approximation ratio has a multiplicative factor of $O(\sqrt{d})$ and the update time should be of the form $O(n^{\varepsilon d})$.