  We study the on-line minimum weighted bipartite matching problem in arbitrary
metric spaces. Here, $n$ not necessary disjoint points of a metric space $M$
are given, and are to be matched on-line with $n$ points of $M$ revealed one by
one. The cost of a matching is the sum of the distances of the matched points,
and the goal is to find or approximate its minimum. The competitive ratio of
the deterministic problem is known to be $\Theta(n)$. It was conjectured that a
randomized algorithm may perform better against an oblivious adversary, namely
with an expected competitive ratio $\Theta(\log n)$. We prove a slightly weaker
result by showing a $o(\log^3 n)$ upper bound on the expected competitive
ratio. As an application the same upper bound holds for the notoriously hard
fire station problem, where $M$ is the real line.
