Online Metric Matching with Delay

Abstract

Traditionally, an online algorithm must service a request upon its arrival. In many practical situations, one can delay the service of a request in the hope of servicing it more efficiently in the near future. As a result, the study of online algorithms with delay has recently gained considerable traction. For most online problems with delay, competitive algorithms have been developed that are independent of properties of the delay functions associated with each request. Interestingly, this is not the case for the online min-cost perfect matching with delays (MPMD) problem, introduced by Emek et al.(STOC 2016).

In this thesis we show that some techniques can be modified to extend to larger classes of delay functions, without affecting the competitive ratio. In the interest of designing competitive solutions for the problem in a more general setting, we introduce the study of online problems with set delay. Here, the delay cost at any time is given by an arbitrary function of the set of pending requests, rather than the sum over individual delay functions associated with each request. In particular, we study the online min-cost perfect matching with set delay (MPMD-Set) problem, which provides a generalisation of MPMD. In contrast to previous work, the new model allows us to study the problem in the non-clairvoyant setting, i.e. where the future delay costs are unknown to the algorithm. We prove that for MPMD-Set in the most general non-clairvoyant setting, there exists no competitive algorithm. Motivated by this impossibility, we introduce a new class of delay functions called sizebased and prove that for this version of the problem, there exist both non-clairvoyant deterministic and randomised algorithms that are competitive in the number of requests. Our results reveal that the quality of an online matching depends both on the algorithm's access to information about future delay costs, and the properties of the delay function.