Learning augmented methods for matching: Improving invasive species management and urban mobility
With the success of machine learning, integrating learned models into real-world systems has become a critical chal- lenge. Naively applying predictions to combinatorial opti- mization problems can incur high costs, which has motivated researchers to consider learning augmented algorithms that can make use of faulty or incomplete predictions. Inspired by two matching problems in computational sustainability where data are abundant, we consider the learning augmented min weight matching problem where some nodes are revealed online while others are known a priori, e.g., by being pre- dicted by machine learning. We develop an algorithm that is able to make use of this extra information and provably im- proves upon pessimistic online algorithms. We evaluate our algorithm on two settings from computational sustainability – the coordination of opportunistic citizen scientists for inva- sive species management and the matching between taxis and riders under uncertain trip duration predictions. In both cases, we perform extensive experiments on real-world datasets and find that our method outperforms baselines, showing how learning augmented algorithms can reliably improve solu- tions for problems in computational sustainability