3
[2310.19514] Approximate Earth Mover's Distance in Truly-Subquadratic Time
source link: https://arxiv.org/abs/2310.19514
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Computer Science > Data Structures and Algorithms
[Submitted on 30 Oct 2023 (v1), last revised 10 Nov 2023 (this version, v3)]
Approximate Earth Mover's Distance in Truly-Subquadratic Time
We design an additive approximation scheme for estimating the cost of the min-weight bipartite matching problem: given a bipartite graph with non-negative edge costs and ε>0, our algorithm estimates the cost of matching all but O(ε)-fraction of the vertices in truly subquadratic time O(n2−δ(ε)).
Our algorithm has a natural interpretation for computing the Earth Mover's Distance (EMD), up to a ε-additive approximation. Notably, we make no assumptions about the underlying metric (more generally, the costs do not have to satisfy triangle inequality). Note that compared to the size of the instance (an arbitrary n×n cost matrix), our algorithm runs in {\em sublinear} time.
Our algorithm can approximate a slightly more general problem: max-cardinality bipartite matching with a knapsack constraint, where the goal is to maximize the number of vertices that can be matched up to a total cost B.
| Subjects: | Data Structures and Algorithms (cs.DS); Computational Geometry (cs.CG) |
| Cite as: | arXiv:2310.19514 [cs.DS] |
| (or arXiv:2310.19514v3 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2310.19514 |
Submission history
From: Lorenzo Beretta [view email][v1] Mon, 30 Oct 2023 13:13:03 UTC (366 KB)
[v2] Thu, 2 Nov 2023 15:01:49 UTC (367 KB)
[v3] Fri, 10 Nov 2023 22:53:39 UTC (366 KB)
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK