论文标题
在（随机订单）在线争夺分辨率方案（两分）图的匹配多元
On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs
论文作者
论文摘要
当元素被顺序呈现给算法时，在线争论解决方案（OCRS）代表了选择元素的一部分，但要遵守资源约束。 OCRS导致了在线资源分配问题的一些最著名的竞争比保证，并以统一的方式处理不同的在线决策（接受/拒绝，搜索，定价），并获得了额外的好处。本文分析了OCRS的资源约束，这些匹配是图形中的匹配定义的，这是组合优化的基本结构。我们考虑变体的两个维度：以对抗性或随机顺序呈现的元素；图形是双方或一般的。无论是在算法保证和不可能的结果方面，我们都会改善各种变体组合的艺术状态。与可以选择到达或离线顺序的争夺解决方案相比，我们的某些算法保证也是最著名的。总而言之，我们对OCR的结果直接提高了以统一的方式在线接受，拒绝，探测和定价问题的最著名的竞争比率。
Online Contention Resolution Schemes (OCRS's) represent a modern tool for selecting a subset of elements, subject to resource constraints, when the elements are presented to the algorithm sequentially. OCRS's have led to some of the best-known competitive ratio guarantees for online resource allocation problems, with the added benefit of treating different online decisions -- accept/reject, probing, pricing -- in a unified manner. This paper analyzes OCRS's for resource constraints defined by matchings in graphs, a fundamental structure in combinatorial optimization. We consider two dimensions of variants: the elements being presented in adversarial or random order; and the graph being bipartite or general. We improve the state of the art for all combinations of variants, both in terms of algorithmic guarantees and impossibility results. Some of our algorithmic guarantees are best-known even compared to Contention Resolution Schemes that can choose the order of arrival or are offline. All in all, our results for OCRS directly improve the best-known competitive ratios for online accept/reject, probing, and pricing problems on graphs in a unified manner.
