On (Random-Order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs
成果类型：
Article
署名作者：
MacRury, Calum; Ma, Will; Grammel, Nathaniel
署名单位：
Columbia University; Columbia University; University System of Maryland; University of Maryland College Park
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.2023.0339
发表日期：
2025
关键词：
摘要：
Online Contention Resolution Schemes (OCRSs) represent a modern tool for selecting a subset of elements, subject to resource constraints, when the elements are presented to the algorithm sequentially. OCRSs 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 OCRSs 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 with Contention Resolution Schemes that can choose the order of arrival or are offline. All in all, our results for OCRSs directly improve the bestknown competitive ratios for online accept/reject, probing, and pricing problems on graphs in a unified manner.