In this paper, we study the online min-cost perfect matching with delay (MPMD) problem where $m$ requests arrive in a metric space of $n$ points. In MPMD, an algorithm can choose to match a request or delay it, aiming to minimize the total costs of connection and delay. The connection cost is the distance between two matched requests in the metric, while the delay cost increases as a function of the set of unmatched requests.
We investigate two types of delay functions: size-based (MPMD-Size) and convex delays (MPMD-Convex). The study of MPMD-Size was initiated by Deryckere and Umboh at the APPROX/RANDOM 2023 conference, where the instantaneous delay increment is a non-negative monotone function of unmatched requests. Our bounds are in terms of $n$, contrasting Deryckere and Umboh's bounds that depend on $m$. Our results settle the deterministic competitive ratio up to constants.
At the heart of these results is a succinct encoding scheme of MPMD-Size on a given $n$-point metric as a metrical task system problem on a $2^{n-1}$-point metric. We also consider MPMD-Convex proposed by Liu et al., where the delay cost incurred by each request is a uniform convex delay function of the time difference between its arrival and the moment it is matched. They focused on delay functions $f$ that are unbounded, non-decreasing, continuous, and satisfy $f(0)=f'(0)=0$, showing that the deterministic competitive ratio is $\Omega(n)$ for $n$-point uniform metrics.
Surprisingly, when $f$ is a non-negative, monotone polynomial with $f'(0) > 0$, there exists an $O(1)$-competitive deterministic algorithm for uniform metrics. Our result completes the understanding of MPMD-Convex on uniform metrics for a broad class of functions.
Blogger's Review: This paper demonstrates an in-depth study of handling delay costs in online matching problems, particularly in the context of size-based and convex functions. With clear theoretical bounds and algorithm constructions, it provides significant insights and references for further research in related fields, making it a noteworthy contribution.