AI summaryⓘ
The authors study a problem where requests appear over time in different locations, and the goal is to pair them up while minimizing travel distance and waiting time costs. They focus on two types of waiting cost models: one based on how many requests are unmatched (MPMD-Size) and another where waiting costs grow in a convex way with time (MPMD-Convex). For MPMD-Size, the authors provide new performance bounds based on the number of points in the space, improving previous results. For MPMD-Convex, they show that under certain polynomial delay functions, it is possible to design algorithms that perform well on uniform spaces, completing earlier work that suggested such problems were harder. Overall, their work advances understanding of how delay costs affect online matching strategies.
online min-cost perfect matchingmetric spacedelay costdeterministic competitive ratiometrical task systemconvex delay functionsuniform metricpolynomial delayonline algorithmsapproximation bounds
Authors
Junhao Gan, Xiao Sun, Seeun William Umboh
Abstract
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 to delay, and the objective is to minimise the sum of connection and delay costs. The connection cost of a match is the distance between the locations of two matched requests in the metric, and the increase of the delay cost is a function of the set of unmatched requests at every moment. In this paper, we study two different types of delay functions, size-based (MPMD-Size) and convex delays (MPMD-Convex). The study of MPMD-Size was initiated by Deryckere and Umboh (APPROX/RANDOM 2023) where the instantaneous delay increment is a non-negative monotone function of the number of unmatched requests. Our bounds are in terms of $n$, as opposed to 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. (ISAAC 2018) where the delay cost incurred by each request is a uniform convex delay function of the time difference between its arrival time and the moment that it is matched by the algorithm. They focused on delay functions $f$ that are unbounded, non-decreasing, continuous, and satisfy $f(0)=f'(0)=0$, and showed that the deterministic competitive ratio is $Ω(n)$ for $n$-point uniform metrics. We show that, surprisingly, when $f$ is a non-negative, monotone polynomial with $f'(0)>0$, there is an $O(1)$-competitive deterministic algorithm for uniform metrics. Our result completes our understanding of MPMD-Convex on uniform metrics for a broad class of functions.