A Collection of Lower Bounds for Online Matching on the Line

Antonios Antoniadis, Carsten Fischer, Andreas Tönnis

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.

A local interval $I_r$ defined by the nearest available servers $s_L$ and $s_R$.

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.

Recursive construction of adversarial instances $T_2$ and $\bar{T}_2$ used to force logarithmic costs across multiple levels.

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

Abstract

In the online matching on the line problem, the task is to match a set of requests R online to a given set of servers S. The distance metric between any two points in $$R\,\cup \,S$$ is a line metric and the objective for the online algorithm is to minimize the sum of distances between matched server-request pairs. This problem is well-studied and – despite recent improvements – there is still a large gap between the best known lower and upper bounds: The best known deterministic algorithm for the problem is $$O(\log ^2n)$$ -competitive, while the best known deterministic lower bound is 9.001. The lower and upper bounds for randomized algorithms are 4.5 and $$O(\log n)$$ respectively. We prove that any deterministic online algorithm which in each round: (i) bases the matching decision only on information local to the current request, and (ii) is symmetric (in the sense that the decision corresponding to the mirror image of some instance I is the mirror image of the decision corresponding to instance I), must be $$\varOmega (\log n)$$ -competitive. We then extend the result by showing that it also holds when relaxing the symmetry property so that the algorithm might prefer one side over the other, but only up to some degree. This proves a barrier of $$\varOmega (\log n)$$ on the competitive ratio for a large class of “natural” algorithms. This class includes all deterministic online algorithms found in the literature so far. Furthermore, we show that our result can be extended to randomized algorithms that locally induce a symmetric distribution over the chosen servers. The $$\varOmega (\log n)$$ -barrier on the competitive ratio holds for this class of algorithms as well.
BibTeX
@inproceedings{antoniadis2018collection,
  author = {Antonios Antoniadis and Carsten Fischer and Andreas Tönnis},
  title = {{A Collection of Lower Bounds for Online Matching on the Line}},
  booktitle = {LATIN},
  year = {2018},
  doi = {10.1007/978-3-319-77404-6\_5},
}
Figure