An algorithm that achieves the minimum and runs
O(n2.5) time has long been available [Vai89].
This was improved to
O(n1.5log5n) in [Var98].
Recently Arora showed how to achieve a
(1 + ε)-approximation
n(log n)O(1/ε) time [Aro98],
and this has been improved to
O((n/ε3)log6n) 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.
O(n2+ε) has been achieved [AES99],
(1 + ε)-approximation can be found in
O((n/ε)1.5log5n) time [VA99].