Computer Science – Data Structures and Algorithms
Scientific paper
2007-05-31
Computer Science
Data Structures and Algorithms
to be published
Scientific paper
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.
Csaba Béla
Pluhár András S.
No associations
LandOfFree
A randomized algorithm for the on-line weighted bipartite matching problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A randomized algorithm for the on-line weighted bipartite matching problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A randomized algorithm for the on-line weighted bipartite matching problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-289446