A randomized algorithm for the on-line weighted bipartite matching problem

A randomized algorithm for the on-line weighted bipartite matching problem

0.00 Avg rating0 Votes
Article ID: iaor200964612
Country: United Kingdom
Volume: 11
Issue: 6
Start Page Number: 449
End Page Number: 455
Publication Date: Dec 2008
Journal: Journal of Scheduling
Authors: ,
Keywords: matching
Abstract:

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 Θ(n). It was conjectured in 1998 that a randomized algorithm may perform better against an oblivious adversary, namely with an expected competitive ratio Θ(logn). We prove a slightly weaker result by showing a o(log3n) 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.

Reviews

Required fields are marked *. Your email address will not be published.