Randomized online algorithms for minimum metric bipartite matching
Adam Meyerson, Akash Nanavati, Laura Poplawski · 2006
We present the rst poly-logarithmic competitive online algorithm for minimum metric bipartite matching. Via induction and a careful use of potential functions, we show that a simple randomized greedy algorithm is competitive on a hierarchically separated tree. Application of recent results on randomized embedding of metrics into trees yield the poly-logarithmic result for general metrics. 1