Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model

arXiv2206.11397MaRDI QIDQ6402903

Author name not available (Why is that?)

Publication date: 22 June 2022

Abstract: We study the two-stage vertex-weighted online bipartite matching problem of Feng, Niazadeh, and Saberi (SODA 2021) 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 $0leqRleqfrac34$ and $sqrt1-R+sqrt1-C=1$, and prove that no other algorithm can achieve a better tradeoff.

Has companion code repository: https://github.com/mapleox/matching_predictions

This page was built for publication: Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6402903)