7
$\begingroup$

I am given two sets $S, T$ each of $n$ points in $\mathbb{R}^k$, I want to find a bijection $a : S \rightarrow T$, such that $$\sum_{s \in S} d(s, a(s))$$ gets minimized, with $d$ being the Euclidean distance.

I am aware that this transportation problem is a special case of the earth mover distance problem, but since its unweighted (and over points) I am wondering if there is a more efficient algorithm than the cubic time hungarian method for it?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ For $d=1$ there's an easy greedy algorithm with $O(n \log n)$ running time. Maybe it's worth thinking about $d=2$ as the simplest interesting (non-trivial) case. $\endgroup$
    – D.W. ♦
    Commented Oct 26, 2016 at 7:28
  • $\begingroup$ I doubt it. I was reading a paper from 2014 that needed to solve exactly this as a subproblem, and they used the $O(n^3)$ Hungarian algorithm. $\endgroup$
    – j_random_hacker
    Commented Oct 26, 2016 at 10:19
  • $\begingroup$ As a very special case: If $d=2$ you can build the convex hull on the set of all $2n$ points in $O(n\log n)$ time, and then calculate the total distance for each of the 2 possible alternating paths of edges around the hull. If it happens that the smaller of these is a valid solution, it must be optimal. (Obviously this is an even stronger requirement than that the points must all lie on the convex hull, which is already a very strong condition...) $\endgroup$
    – j_random_hacker
    Commented Oct 26, 2016 at 10:23
  • $\begingroup$ You might want to change it to $\mathbb{R}^k$ or something since you're using $d$ for the metric $\endgroup$
    – MT_
    Commented Oct 26, 2016 at 15:08

1 Answer 1

Reset to default
4
$\begingroup$

As mentioned in the problem statement, this is the Assignment Problem (minimum weight bipartite matching) where it is known that the weights are the Euclidean distances.

There have been several improvements since the Hungarian Algorithm, at least in terms of asymptotic bounds. Depending on the exact size of the graph, any of several algorithms may be the best. A table in the paper by Cohen, et al gives details. Edmonds and Karp's algorithm is $O(nm + n^2 log n)$, and is still the best bound that doesn't depend on the maximum weight in the graph. Cohen's algorithm appears to be the best for sparse graphs, which is not your situation. I think the best for your dense graph would be Sankowski's $\tilde{O} (W n^\omega)$, since it doesn't depend on $m$.

I do not know if there are ways to exploit this problem's specific weight structure (Euclidean distances) for further improvements.

Sources:

Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in $\tilde{O}(m^{(10/7)} log W)$ Time. Michael B. Cohen, Aleksander Madry, Piotr Sankowski, Adrian Vladu
https://arxiv.org/abs/1605.01717v3 (preprint)

J. Edmonds and R.M. Karp. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. J. ACM, 19(2):248–264, 1972.

Piotr Sankowski. Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I, chapter Weighted Bipartite Matching in Matrix Multiplication Time, pages 274–285. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006.
http://link.springer.com/chapter/10.1007%2F11786986_25

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.