On (Random-Order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs

Calum MacRury (), Will Ma () and Nathaniel Grammel ()
Additional contact information
Calum MacRury: Graduate School of Business, Columbia University, New York, New York 10027
Will Ma: Graduate School of Business, Columbia University, New York, New York 10027; and Data Science Institute, Columbia University, New York, New York 10027
Nathaniel Grammel: Department of Computer Science, University of Maryland, College Park, Maryland 20742

Operations Research, 2025, vol. 73, issue 2, 689-703

Abstract: 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 best-known competitive ratios for online accept/reject, probing, and pricing problems on graphs in a unified manner.

Keywords: Market; Analytics; and; Revenue; Management; prophet inequalities; contention resolution schemes; online matching; randomized rounding; random graphs (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2023.0339 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:73:y:2025:i:2:p:689-703

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().