Timezone: »
Poster
Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model
Billy Jin · Will Ma
We study the two-stage vertex-weighted online bipartite matching problem of Feng, Niazadeh, and Saberi (SODA ‘21) in a setting where the algorithm has access to a suggested matching that is recommended in the first stage. We evaluate an algorithm by its robustness $R$, which is its performance relative to that of the optimal offline matching, and its consistency $C$, which is its performance when the advice or the prediction given is correct. We characterize for this problem the Pareto-efficient frontier between robustness and consistency, which is rare in the literature on advice-augmented algorithms, yet necessary for quantifying such an algorithm to be optimal. Specifically, we propose an algorithm that is $R$-robust and $C$-consistent for any $(R,C)$ with $0 \leq R \leq \frac{3}{4}$ and $\sqrt{1-R} + \sqrt{1-C} = 1$, and prove that no other algorithm can achieve a better tradeoff.
Author Information
Billy Jin (Cornell University)
Will Ma (Columbia University)
More from the Same Authors
-
2022 Poster: Beyond IID: data-driven decision-making in heterogeneous environments »
Omar Besbes · Will Ma · Omar Mouchtaki -
2021 Poster: High Probability Complexity Bounds for Line Search Based on Stochastic Oracles »
Billy Jin · Katya Scheinberg · Miaolan Xie -
2021 Poster: Improved Guarantees for Offline Stochastic Matching via new Ordered Contention Resolution Schemes »
Brian Brubach · Nathaniel Grammel · Will Ma · Aravind Srinivasan -
2020 Poster: The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verification »
Christian Tjandraatmadja · Ross Anderson · Joey Huchette · Will Ma · KRUNAL KISHOR PATEL · Juan Pablo Vielma