# Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line

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

## Key facts

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

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

- [Parsimonious Learning-Augmented Online Metric Matching](https://mlsanity.com/paper/2605.26886/) (2026)

## Abstract (arXiv)

In the online metric bipartite matching problem, we are given a set S of server locations in a metric space. Requests arrive one at a time, and on its arrival, we need to immediately and irrevocably match it to a server at a cost which is equal to the distance between these locations. A α-competitive algorithm will assign requests to servers so that the total cost is at most α times the cost of MOPT where MOPT is the minimum cost matching between S and R. We consider this problem in the adversarial model for the case where S and R are points on a line and |S|=|R|=n. We improve the analysis of the deterministic Robust Matching Algorithm (RM-Algorithm, Nayyar and Raghvendra FOCS'17) from O(log2 n) to an optimal Theta(log n). Previously, only a randomized algorithm under a weaker oblivious adversary achieved a competitive ratio of O(log n) (Gupta and Lewi, ICALP'12). The well-known Work Function Algorithm (WFA) has a competitive ratio of O(n) and Omega(log n) for this problem. Therefore, WFA cannot achieve an asymptotically better competitive ratio than the RM-Algorithm.