Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910683930558464 |
|---|---|
| author | Jin, Billy Ma, Will |
| author_facet | Jin, Billy Ma, Will |
| contents | Two-stage bipartite matching is a fundamental problem of optimization under uncertainty introduced by Feng, Niazadeh, and Saberi (2021), who study it under the stochastic and adversarial paradigms of uncertainty. We propose a method to interpolate between these paradigms, using the Algorithms with Predictions (ALPS) framework. To elaborate, given some form of information (e.g. a distributional prediction) about the uncertainty, we consider the optimal decision assuming that information is correct to be some "advice", whose accuracy is unknown. In the ALPS framework, we define Consistency to be an algorithm's performance relative to the advice, and Robustness to be an algorithm's performance relative to the hindsight-optimal decision. We characterize the tight tradeoff between Consistency and Robustness for four settings of two-stage matching: unweighted, vertex-weighted, edge-weighted, and fractional budgeted allocation. Additionally, we show our algorithm achieves state-of-the-art performance in both synthetic and real-data simulations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2206_11397 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model Jin, Billy Ma, Will Data Structures and Algorithms Optimization and Control Two-stage bipartite matching is a fundamental problem of optimization under uncertainty introduced by Feng, Niazadeh, and Saberi (2021), who study it under the stochastic and adversarial paradigms of uncertainty. We propose a method to interpolate between these paradigms, using the Algorithms with Predictions (ALPS) framework. To elaborate, given some form of information (e.g. a distributional prediction) about the uncertainty, we consider the optimal decision assuming that information is correct to be some "advice", whose accuracy is unknown. In the ALPS framework, we define Consistency to be an algorithm's performance relative to the advice, and Robustness to be an algorithm's performance relative to the hindsight-optimal decision. We characterize the tight tradeoff between Consistency and Robustness for four settings of two-stage matching: unweighted, vertex-weighted, edge-weighted, and fractional budgeted allocation. Additionally, we show our algorithm achieves state-of-the-art performance in both synthetic and real-data simulations. |
| title | Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model |
| topic | Data Structures and Algorithms Optimization and Control |
| url | https://arxiv.org/abs/2206.11397 |