Abstract: This paper establishes a significant performance floor for a large class of "natural" algorithms in Online Matching on the Line (OML). By constructing recursive adversarial instances, the authors prove that any algorithm relying on local information and symmetry is fundamentally limited to a competitive ratio of $\Omega(\log n)$ relative to an optimal offline solution.
Introduction
Online Matching on the Line (OML) is a fundamental problem in computer science with practical applications ranging from resource allocation to logistics. Imagine a ski rental shop where customers of varying heights arrive sequentially; each must be immediately assigned a pair of skis from the current stock to minimize the total difference between customer heights and ski lengths.
Despite its importance, a significant gap has persisted between theory and practice. While the best deterministic algorithms achieve a competitive ratio of $O(\log^2 n)$, the best known lower bound was previously a small constant. This paper aims to close this gap by demonstrating that most commonly used algorithms are fundamentally limited to logarithmic performance.
The Locality Trap
The authors focus on Local Algorithms, which make matching decisions based solely on the "local interval"—the space between the nearest available server to the left ($s_L$) and the nearest to the right ($s_R$) of a new request.
Locality is often preferred because using global information is computationally expensive. However, this research shows that locality allows an adversary to "trick" an algorithm into making expensive matches at every scale of the problem. If an algorithm is symmetric—treating left and right identically—an adversary can mirror the instance to ensure the algorithm consistently chooses the suboptimal side of a local interval.
Recursive Adversarial Construction
The core of the proof relies on a recursive binary tree construction. The authors design an adversarial instance where requests are placed precisely between two subtrees, forcing the algorithm to match the request to one of the two furthest servers in those subtrees. This "bad" decision is repeated at every level of the recursion, accumulating to the $\Omega(\log n)$ bound.
Key Results
The paper presents three primary theorems that define the limits of natural algorithms:
- Theorem 1: Any deterministic, local, and symmetric algorithm is $\Omega(\log n)$-competitive.
- Theorem 2: This bound holds even for non-symmetric algorithms, provided their preference bias for one side does not grow exponentially (specifically, by more than a factor of 2) as problem depth increases.
- Theorem 3: Randomized local algorithms that maintain symmetric probability distributions over available servers (such as the HARMONIC algorithm) are also limited to $\Omega(\log n)$.
These results explain why existing practical algorithms like the Work Function Algorithm (WFA) and t-net-cost have struggled to break the logarithmic barrier.
Limitations and Future Work
The primary limitation of these bounds is their specificity to local algorithms. The authors acknowledge that a "non-local" algorithm—one that considers the positions of matched servers or distant free servers—might be able to break the $\Omega(\log n)$ barrier.
Future research should focus on two paths: designing non-local strategies that effectively utilize global information and tightening the analysis to determine if the true optimal competitive ratio for OML is $\log n$ or $\log^2 n$.
Summary updated