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^*$.
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.
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