论文标题
在线双方匹配与建议：两阶段模型的紧密稳定性折衷方案
Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model
论文作者
论文摘要
两阶段的两分匹配是Feng，Niazadeh和Saberi（2021）引入的不确定性中优化的基本问题，他们在不确定性的随机和对抗性范式下进行了研究。我们提出了一种使用具有预测（ALP）框架的算法，将这些范式插值的方法。为了详细说明，鉴于有关不确定性的某种形式的信息（例如分配预测），我们认为最佳决定假设信息是正确的，即某些“建议”，其准确性是未知的。在阿尔卑斯山框架中，我们将一致性定义为相对于建议的算法的性能，并且鲁棒性是算法相对于事后最佳决定的算法的性能。我们表征了两阶段匹配的四个设置的一致性和鲁棒性之间的紧缩权衡：未加权，顶点加权，边缘加权和部分预算分配。此外，我们显示了我们的算法在合成和真实数据模拟中都达到了最先进的性能。
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.
