ﻻ يوجد ملخص باللغة العربية
The Earth Mover Distance (EMD) between two sets of points $A, B subseteq mathbb{R}^d$ with $|A| = |B|$ is the minimum total Euclidean distance of any perfect matching between $A$ and $B$. One of its generalizations is asymmetric EMD, which is the minimum total Euclidean distance of any matching of size $|A|$ between sets of points $A,B subseteq mathbb{R}^d$ with $|A| leq |B|$. The problems of computing EMD and asymmetric EMD are well-studied and have many applications in computer science, some of which also ask for the EMD-optimal matching itself. Unfortunately, all known algorithms require at least quadratic time to compute EMD exactly. Approximation algorithms with nearly linear time complexity in $n$ are known (even for finding approximately optimal matchings), but suffer from exponential dependence on the dimension. In this paper we show that significant improvements in exact and approximate algorithms for EMD would contradict conjectures in fine-grained complexity. In particular, we prove the following results: (1) Under the Orthogonal Vectors Conjecture, there is some $c>0$ such that EMD in $Omega(c^{log^* n})$ dimensions cannot be computed in truly subquadratic time. (2) Under the Hitting Set Conjecture, for every $delta>0$, no truly subquadratic time algorithm can find a $(1 + 1/n^delta)$-approximate EMD matching in $omega(log n)$ dimensions. (3) Under the Hitting Set Conjecture, for every $eta = 1/omega(log n)$, no truly subquadratic time algorithm can find a $(1 + eta)$-approximate asymmetric EMD matching in $omega(log n)$ dimensions.
We consider the complexity properties of modern puzzle games, Hexiom, Cut the Rope and Back to Bed. The complexity of games plays an important role in the type of experience they provide to players. Back to Bed is shown to be PSPACE-Hard and the firs
We study the problem of approximating the value of a Unique Game instance in the streaming model. A simple count of the number of constraints divided by $p$, the alphabet size of the Unique Game, gives a trivial $p$-approximation that can be computed
The analysis of several algorithms and data structures can be framed as a peeling process on a random hypergraph: vertices with degree less than k and their adjacent edges are removed until no vertices of degree less than k are left. Often the questi
In this work, we show the first worst-case to average-case reduction for the classical $k$-SUM problem. A $k$-SUM instance is a collection of $m$ integers, and the goal of the $k$-SUM problem is to find a subset of $k$ elements that sums to $0$. In t
A homomorphism from a graph G to a graph H is a vertex mapping f from the vertex set of G to the vertex set of H such that there is an edge between vertices f(u) and f(v) of H whenever there is an edge between vertices u and v of G. The H-Colouring p