# Online Matching: Haste makes Waste!

arXiv: https://arxiv.org/abs/1603.03024 · HTML: https://mlsanity.com/paper/1603.03024/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Mar 2016.

## Built on by (most cited first, 1 of 1)

- [Delayed Assignments in Online Non-Centroid Clustering with Stochastic Arrivals](https://mlsanity.com/paper/2601.16091/) (2026)

## Abstract (arXiv)

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 Delta), where n is the number of points in M and Delta 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.