Links
- More information: Publisher Index Page
- Download citation as: RIS | Dublin Core
Abstract
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
Study Area
| Publication type | Conference Paper |
|---|---|
| Publication Subtype | Conference Paper |
| Title | Learning augmented methods for matching: Improving invasive species management and urban mobility |
| Volume | 35 |
| Issue | 17 |
| Year Published | 2021 |
| Language | English |
| Publisher | Association for the Advancement of Artificial Intelligence |
| Contributing office(s) | Coop Res Unit Leetown |
| Description | 9 p. |
| Larger Work Type | Book |
| Larger Work Subtype | Conference publication |
| Larger Work Title | Proceedings of the AAAI conference on artificial intelligence |
| First page | 14702 |
| Last page | 14710 |
| Conference Title | AAAI conference on artificial intelligence |
| Conference Location | Online |
| Conference Date | February 2-9, 2021 |
| Country | United States |
| State | New York |
| Google Analytic Metrics | Metrics page |