A Deterministic Polylogarithmic Competitive Algorithm for Matching with Delays

Marc Dufay, Roger Wattenhofer · 2025

Read A Deterministic Polylogarithmic Competitive Algorithm for Matching with Delays by Marc Dufay, Roger Wattenhofer (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-20588.txt.

Introduction

Marc Dufay and Roger Wattenhofer study an online matching task where requests arrive over time in a space whose shape may not be known in advance. Each request must be paired with another, and the cost counts both the distance between pairs and how long each request waited to be matched.

Earlier methods for unknown spaces paid a cost that grew fast with the number of requests, far above the known lower bound. Dufay and Wattenhofer give a fixed rule method with cost that grows only as a small power of a logarithm, a huge step toward the bound. The method needs no advance knowledge of the space or the request count.

Catalog record

CREATORMarc Dufay, Roger Wattenhofer
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE103 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-20588

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Deterministic Polylogarithmic Competitive Algorithm for Matching with Delays Marc Dufay, Roger Wattenhofer Abstract In the online Min-cost Perfect Matching with Delays ( MPMD ) problem, m m requests in a metric space are submitted at different times by an adversary. The goal is to match all requests while (i) minimizing the sum of the distances between matched pairs as well as (ii) how long each request remained unmatched after it appeared. While there exist almost optimal algorithms when the metric space is finite and known a priori, this is not the case when the metric space is infinite or unknown. In this latter case, the best known algorithm, due to Azar and Jacob-Fanani, has competitiveness 𝒪 ⁡ ( m 0.59 ) \mathcal{O}(m^{0.59}) which is exponentially worse than the best known lower bound of Ω ⁡ ( log ⁡ m / log ⁡ log ​ m ) \Omega(\log m/\log\log m) by Ashlagi et al. We present a 𝒪 ⁡ ( log 5 ⁡ m ) \mathcal{O}(\log^{5}m) -competitive algorithm for the MPMD problem. This algorithm is deterministic and does not need to know the metric space or m m in advance. This is an exponential improvement over previous results and only a polylogarithmic factor away from the lower bound. 1 Introduction We consider an online two-player game like online chess or racing. Players arrive one by one and must be paired to play games against each other. A well-designed matchmaking system needs to optimize two conflicting criteria: first, we need to minimize the players’ waiting time to maintain engagement, second, we need to ensure that players are satisfied with whom they are matched with. This satisfaction might depend on multiple factors, e.g., the skill difference with their opponent or their geographical distance, which affects game latency. This trade-off was first formalized by Emek et al [ 8 ] by defining the online Min-cost Perfect Matching with Delay ( MPMD ) problem. In this problem we are given a metric space and m requests, which are points in the metric space arriving at any time. An algorithm must pair all requests in a way that minimizes (i) the sum of the distances between each pair (space cost) and (ii) how long each request has to wait after arriving before being matched (time cost). This problem was first studied in the case where the metric space is finite and known in advance. Most of the proposed algorithms were randomized and relied on metric tree embeddings [ 8 , 2 ] . We note that this approach has many drawbacks. First, the competitive ratio may be arbitrarily large compared to the actual number of requests. In addition, these algorithms’ guarantees only hold in expectation. In particular, these algorithms fail against an adaptive adversary. A way to work around these issues is to no longer assume knowledge about the metric space and focus on deterministic algorithms. This line of work started with Bienkowski et al [ 6 ] who gave an algorithm with \mathcal{O}(m^{\log 5.5})\approx\mathcal{O}(m^{2.46}) competitiveness. This was later improved to \mathcal{O}(m) by Bienkowski et al [ 5 ] and to \mathcal{O}(\varepsilon^{-1}m^{\log(1.5+\varepsilon)})\approx\mathcal{O}(m^{0.59}) by Azar and Jacob-Fanani [ 3 ] . This is so far the best competitiveness for the general MPMD problem. A lower bound of \Omega(\log m/\log\log m) also exists by Ashlagi et al [ 1 ] . This lower bound is quite strong as it holds even for a randomized algorithm against an oblivious adversary. 1.1 Our contribution In their paper [ 3 ] , Azar and Jacob-Fanani ask whether there exists an algorithm with poly-logarithmic competitiveness in the general setting. We answer in the positive by describing a deterministic algorithm with \mathcal{O}(\log^{5}m) -competitiveness for MPMD . This represents an exponential improvement over previous results and is only a poly-logarithmic factor away from the best known lower bound of \Omega(\log m/\log\log m) . 1.2 Related Work The first algorithm with bounded competitive ratio was given by Emek et al [ 8 ] and focuses on the case where the metric space is known, finite of size n and the adversary is oblivious. In this case, they give a randomized \mathcal{O}(\log^{2}n+\log\Delta) -competitive algorithm, where \Delta is the aspect ratio of the metric space. This was later improved to \mathcal{O}(\log n) by [ 2 ] . These algorithms use the same approach of embedding the metric space in a tree with logarithmic distortion. Regarding lower bounds, [ 2 ] first gave an \Omega(\sqrt{\log n}) lower bound which was later improved to \Omega(\log n/\log\log n) by Ashlagi et al [ 1 ] . These lower bounds hold for a randomized algorithm against an oblivious adversary. Moreover, because the latter bound uses m=\Theta(n) requests, it also implies the \Omega(\log m/\log\log m) bound described above. When the delay cost is a concave function instead of a linear one, Azar et al [ 4 ] give a randomized \mathcal{O}(\log n) -competitive algorithm. As a more general approach, Deryckere and Umboh [ 7 ] consider the MPMD-Set problem, where the time cost at a given instant is a function of the unmatched requests. To work around the logarithmic lower bound, many papers focus on special cases of online matching with delay. For example, for two-point metrics, Emek et al [ 9 ] give an optimal deterministic 3 -competitive algorithm. When the metric space is a tree with height h , Azar et al [ 2 ] provide a deterministic \mathcal{O}(h) -competitive algorithm. If the requests’ arrival times follow a Poisson distribution, Mari et al [ 13 ] give an algorithm with constant competitiveness. For a k -point uniform metric space, Liu et al [ 12 ] give a \mathcal{O}(k) -competitive algorithm which supports convex time cost functions. A closely related problem to the MPMD problem is the online Minimum-cost Bipartite Matching with Delay problem ( MBPMD ). In MBPMD , requests additionally carry a sign (positive or negative) and only requests of opposite sign can be matched. For this problem, Azar et al [ 2 ] first gave a randomized \mathcal{O}(\log n) -competitive algorithm along with a \Omega(\log^{1/3}n) lower bound. This lower bound was later improved to \Omega(\sqrt{\log n/\log\log n}) by Ashlagi et al [ 1 ] . Many results for MPMD , such as the \mathcal{O}(m) -competitive algorithm by Bienkowski et al [ 5 ] and the algorithm with \mathcal{O}(m^{0.59}) -competitiveness by Azar and Jacob-Fanani [ 3 ] have a variant with the same competitiveness for MBPMD . More recently, Kuo [ 11 ] gave an algorithm with \tilde{\mathcal{O}}(\sqrt{m}) -competitiveness for MBPMD on a line. 1.3 Algorithm overview We now give a brief overview of the techniques and ideas used by our algorithm. In essence, the algorithm partitions the requests which arrived so far into components. Requests inside each component are matched using a greedy strategy. Offline approach : Our algorithm can be described as a way to adapt Wattenhofer and Wattenhofer’s algorithm for offline perfect weighted matching [ 17 ] to the online setting. Their algorithm is similar to Boruvska’s algorithm in that we try to cover vertices with components and do so within at most \log n rounds. In each round, some components are merged together to create bigger components. The main difference is that Boruvska’s algorithm

Read the complete text