PERMUTATION Strikes Back: The Power of Recourse in Online Metric Matching

Varun Gupta, Ravishankar Krishnaswamy, Sai Sandeep

Abstract

Online metric matching has long been constrained by the "irrevocability" of assignments, leading to high competitive ratios. This paper introduces recourse—the ability to re-match a small number of clients—to this classic problem. By adapting the PERMUTATION algorithm, the authors demonstrate that logarithmic recourse enables exponential improvements in performance, reducing competitive ratios from $O(k)$ to $O(\log k)$ in general metrics.

Introduction

In the standard Online Metric Matching problem, $k$ servers are fixed in a metric space. As clients arrive sequentially, they must be immediately and irrevocably matched to an available server. This constraint imposes a severe theoretical limit: deterministic algorithms cannot do better than a $2k-1$ competitive ratio. However, in many practical applications, a small amount of re-assignment (recourse) is acceptable. This paper explores how limited recourse can break these decades-old lower bounds.

Methods

The authors build their work on the classic PERMUTATION algorithm, equipping it with recourse strategies to handle different metric environments.

MULTISCALEPERMUTATION (General Metrics)

For general metrics, the algorithm utilizes a binary decomposition of time. It maintains parallel matchings on batches of size $2^i$. When a new client completes a "block," the algorithm re-solves that block optimally. This allows the algorithm to mimic a batched version of the original PERMUTATION, effectively managing the trade-off between cost and re-assignment frequency.

Figure 1: MULTISCALEPERMUTATION block structure and update from $t=11$ to $t=12$.

FARTHESTSERVER (Line Metrics)

On a 1D line, matching can be visualized as a set of arcs. Optimal matchings avoid overlapping forward and backward arcs. The FARTHESTSERVER algorithm "uncrosses" these arcs asymmetrically—only canceling forward arcs when a backward arc is added—to maintain low recourse while achieving a constant competitive ratio.

Figure 2: Matching arc uncrossing in the line metric setting.

Dynamic Matching via HSTs

To handle a fully dynamic setting where both clients and servers can arrive and depart, the authors embed the metric space into Hierarchically Well-Separated Trees (HSTs). They maintain a matching by ensuring that for any subtree, the number of "external" matches corresponds exactly to the local deficit or surplus of clients.

Key Results

The introduction of recourse yields significant theoretical gains across various models:

  • General Metrics: Achieved a $2 \log k$-competitive ratio with $O(\log k)$ per-client recourse. This represents an exponential improvement over the $2k-1$ lower bound for non-recourse algorithms.
  • Line Metrics: Achieved a 3-competitive ratio with $O(\log k)$ amortized recourse, a significant jump over previous deterministic results.
  • Dynamic Setting: For a metric with $n$ points and aspect ratio $\Delta$, the algorithm maintains an $O(\log n)$-competitive ratio with $O(\log \Delta)$ recourse, even under client and server departures.

Conclusion and Future Work

Recourse acts as an "exponential power-up" for online matching algorithms. By allowing a logarithmic number of changes, the performance of the classic PERMUTATION algorithm is drastically enhanced, enabling it to handle dynamic environments and overcome traditional lower bounds. The authors conjecture that for the line metric, it should be possible to achieve an $O(1)$ competitive ratio with $O(1)$ recourse, leaving this as an open area for future exploration.

Summary updated

BibTeX
@inproceedings{gupta2020permutation,
  author = {Varun Gupta and Ravishankar Krishnaswamy and Sai Sandeep},
  title = {{PERMUTATION Strikes Back: The Power of Recourse in Online Metric Matching}},
  booktitle = {APPROX-RANDOM},
  year = {2020},
  doi = {10.4230/lipics.approx/random.2020.40},
}
Figure