Carnegie Mellon University
file.pdf (135.51 kB)

An O (log2k)-Competitive Algorithm for Metric Bipartite Matching

Download (135.51 kB)
journal contribution
posted on 2011-09-01, 00:00 authored by Nikhil Bansal, Niv Buchbinder, Anupam Gupta, Joseph Naor
We consider the online metric matching problem. In this problem, we are given a graph with edge weights satisfying the triangle inequality, and k vertices that are designated as the right side of the matching. Over time up to k requests arrive at an arbitrary subset of vertices in the graph and each vertex must be matched to a right side vertex immediately upon arrival. A vertex cannot be rematched to another vertex once it is matched. The goal is to minimize the total weight of the matching. We give a O(log2 k) competitive randomized algorithm for the problem. This improves upon the best known guarantee of O(log3 k) due to Meyerson, Nanavati and Poplawski [19] . It is well known that no deterministic algorithm can have a competitive less than 2k − 1, and that no randomized algorithm can have a competitive ratio of less than ln k.


Publisher Statement

© 2011 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.



Usage metrics


    Ref. manager