An algorithm that achieves the minimum and runs
in nearly
O(n^{2.5}) time has long been available [Vai89].
This was improved to
O(n^{1.5}log^{5}n) in [Var98].
Recently Arora showed how to achieve a
(1 + ε)-approximation
in
n(log n)^{O(1/ε)} time [Aro98],
and this has been improved to
O((n/ε^{3})log^{6}n) time [VA99].
A special case of considerable interest is bipartite matching,
in which the points are red or blue and the matching connects
points of different color.
Here
O(n^{2+ε}) has been achieved [AES99],
and a
(1 + ε)-approximation can be found in
O((n/ε)^{1.5}log^{5}n) time [VA99].