Online Minimum Cost Matching with Recourse on the Line

Nicole Megow, Lukas NölkeAPPROX-RANDOM 2020 · DOI

Abstract

In the online minimum cost bipartite matching problem on a line, requests arrive sequentially and must be matched to available servers to minimize total distance. Traditionally, this problem faces a $\Theta(\log n)$ competitive ratio barrier. This paper introduces "recourse"—the ability to selectively reassign previous matches—to achieve the first $O(1)$-competitive algorithm. The proposed method utilizes a hierarchical interval structure and an edge-freezing mechanism to maintain a constant competitive ratio with only $O(\log n)$ amortized reassignments per request.

Introduction

Online bipartite matching on a real line is a fundamental problem in resource allocation. When decisions are irrevocable, the best possible competitive ratio is $\Theta(\log n)$. This gap between online and offline performance is significant for real-world applications like ride-sharing. This work explores whether allowing a small amount of "recourse" (reassigning a request to a different server later) can bridge this gap and achieve constant-factor optimality.

Problem Definition

Requests $r_i$ arrive one by one on a 1D line and must be immediately matched to an available server $s_j$. The objective is to minimize $\sum \text{dist}(r_i, s_{\text{matched}(i)})$. In the recourse setting, the algorithm can change the server assigned to a previously matched request, provided the total number of such changes remains low.

Methodology

The core of the proposed approach is a framework that maintains three matchings simultaneously: a recourse matching $M$ (the output), a near-optimal auxiliary matching $M^*$, and a standard online matching $M'$ with no recourse.

Hierarchical Localization

The algorithm groups requests into "aggregate search intervals." Requests in "top blocks" are considered active and matched using the standard online strategy $M'$. As costs grow, requests become inactive and are reassigned in batches to align with the near-optimal $M^*$.

Hierarchical structure of search intervals used to localize the impact of new requests.

Edge Freezing and Stability

To bound the number of reassignments, the authors introduce an "edge freezing" scheme. Cheap edges are "frozen" and excluded from future recourse steps. A key insight is the quadratic growth in stability: an edge frozen at time $i$ typically remains frozen until at least time $i^2$, ensuring that total reassignments are bounded by $O(n \log n)$.

The Algorithm

The algorithm balances current matching costs against future flexibility using a $t$-net-cost function, with $t=3$ providing the optimal balance for $O(1)$ competitiveness.

Algorithm 1: The core logic for handling new requests, freezing edges, and performing recourse steps.

Key Results

The primary contribution is Theorem 1, which proves that the algorithm achieves a constant competitive ratio with an amortized recourse budget of $O(\log n)$ per request. This is the first non-trivial result for min-cost matching with recourse on the line.

For alternating instances (where requests and servers alternate), the authors provide a $(1 + \epsilon)$-competitive algorithm with constant recourse per request ($O(\epsilon^{-1.001})$). Additionally, they show that the $t$-net-cost algorithm is $O(\log \Delta)$-competitive without recourse for alternating instances, where $\Delta$ is the aspect ratio of the metric space.

Conclusion and Future Work

This work demonstrates that a small amount of recourse can fundamentally change the competitive landscape of online matching. While the $O(\log n)$ bound is amortized, future research could investigate whether a strict $O(1)$ recourse limit per request can maintain $O(1)$ competitiveness. The ultimate open question remains whether a randomized $O(1)$ online algorithm exists for the line without any recourse at all.

Summary updated

BibTeX
@inproceedings{megow2020online,
  author = {Nicole Megow and Lukas Nölke},
  title = {{Online Minimum Cost Matching with Recourse on the Line}},
  booktitle = {APPROX-RANDOM},
  year = {2020},
  doi = {10.4230/lipics.approx/random.2020.37},
}
Figure