TY - JOUR

T1 - A randomized O ( log^2 k )-competitive algorithm for metric bipartite matching

AU - Bansal, N.

AU - Buchbinder, N.

AU - Gupta, Anupam

AU - Naor, J.

PY - 2014

Y1 - 2014

N2 - We consider the online metric matching problem in which we are given a metric space, k of whose points are designated as servers. Over time, up to k requests arrive at an arbitrary subset of points in the metric space, and each request must be matched to a server immediately upon arrival, subject to the constraint that at most one request is matched to any particular server. Matching decisions are irrevocable and the goal is to minimize the sum of distances between the requests and their matched servers.
We give an O(log2 k)-competitive randomized algorithm for the online metric matching problem. This improves upon the best known guarantee of O(log3 k) on the competitive factor due to Meyerson, Nanavati and Poplawski (SODA ’06, pp. 954–959, 2006). It is known that for this problem no deterministic algorithm can have a competitive better than 2k-1, and that no randomized algorithm can have a competitive ratio better than lnk.

AB - We consider the online metric matching problem in which we are given a metric space, k of whose points are designated as servers. Over time, up to k requests arrive at an arbitrary subset of points in the metric space, and each request must be matched to a server immediately upon arrival, subject to the constraint that at most one request is matched to any particular server. Matching decisions are irrevocable and the goal is to minimize the sum of distances between the requests and their matched servers.
We give an O(log2 k)-competitive randomized algorithm for the online metric matching problem. This improves upon the best known guarantee of O(log3 k) on the competitive factor due to Meyerson, Nanavati and Poplawski (SODA ’06, pp. 954–959, 2006). It is known that for this problem no deterministic algorithm can have a competitive better than 2k-1, and that no randomized algorithm can have a competitive ratio better than lnk.

U2 - 10.1007/s00453-012-9676-9

DO - 10.1007/s00453-012-9676-9

M3 - Article

VL - 68

SP - 390

EP - 403

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 2

ER -