Parsimonious Learning-Augmented Online Metric Matching

Learning-augmented algorithms have received significant attention in recent years, particularly in the context of online optimization. Motivated by the high computational cost of generating predictions, a growing line of work studies the tradeoff between performance guarantees and the number of predictions used in learning-augmented algorithms for problems such as caching and metrical task systems. In this paper, we extend this line of research to online metric matching by developing parsimonious learning-augmented algorithms and establishing lower bounds on their performance. Our approach extends the Follow-the-Prediction framework to the parsimonious setting by filling in a virtual prediction in the absence of an actual prediction, using an online metric matching algorithm that maintains good intermediate matchings throughout its execution. We complement our theoretical results with an empirical evaluation, demonstrating the practical effectiveness of our approach.

We study how to make better decisions when matching requests to servers, where the requests are revealed one by one over time, while some predictions about the future are available. A motivating example is assigning ride-hailing passengers to drivers. Existing prediction-based algorithms can perform well, but they often assume that a prediction is available at every decision point, which may be expensive or computationally intensive. We develop algorithms that use predictions sparingly, asking for them only occasionally while still using them effectively. Between two actual predictions, our algorithm fills in the missing information using an online algorithm that maintains a high-quality matching throughout its execution. We prove performance guarantees showing how the quality of the solution depends on the number and accuracy of the predictions. We also prove limitations showing that, in some settings, these guarantees are close to the best possible. Experiments on synthetic data and taxi-trip data show that the proposed approach can work well in practice.