Online matching: haste makes waste!

Abstract

This paper studies a new online problem, referred to as min-cost perfect matching with delays (MPMD), defined over a finite metric space (i.e., a complete graph with positive edge weights obeying the triangle inequality) M that is known to the algorithm in advance. Requests arrive in a continuous time online fashion at the points of M and should be served by matching them to each other. The algorithm is allowed to delay its request matching commitments, but this does not come for free: the total cost of the algorithm is the sum of metric distances between matched requests plus the sum of times each request waited since it arrived until it was matched. A randomized online MPMD algorithm is presented whose competitive ratio is O (log2 n + logΔ), where n is the number of points in M and Δ is its aspect ratio. The analysis is based on a machinery developed in the context of a new stochastic process that can be viewed as two interleaved Poisson processes; surprisingly, this new process captures precisely the behavior of our algorithm. A related problem in which the algorithm is allowed to clear any unmatched request at a fixed penalty is also addressed. It is suggested that the MPMD problem is merely the tip of the iceberg for a general framework of online problems with delayed service that captures many more natural problems.