Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark

Mark Braverman, Mahsa Derakhshan, Antonio Molina Lovett

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

In this paper, we study max-weight stochastic matchings on online bipartite graphs under both vertex and edge arrivals. We focus on designing polynomial time approximation algorithms with respect to the online benchmark, which was first considered by Papadimitriou, Pollner, Saberi, and Wajc [EC'21]. In the vertex arrival version of the problem, the goal is to find an approximate max-weight matching of a given bipartite graph when the vertices in one part of the graph arrive online in a fixed order with independent chances of failure. Whenever a vertex arrives we should decide, irrevocably, whether to match it with one of its unmatched neighbors or leave it unmatched forever. There has been a long line of work designing approximation algorithms for different variants of this problem with respect to the offline benchmark (prophet). Papadimitriou et al., however, propose the alternative online benchmark and show that considering this new benchmark allows them to improve the 0.5 approximation ratio, which is the best ratio achievable with respect to the offline benchmark. They provide a 0.51-approximation algorithm which was later improved to 0.526 by Saberi and Wajc [ICALP'21]. The main contribution of this paper is designing a simple algorithm with a significantly improved approximation ratio of (1-1/e) for this problem. We also consider the edge arrival version in which, instead of vertices, edges of the graph arrive in an online fashion with independent chances of failure. Designing approximation algorithms for this problem has also been studied extensively with the best approximation ratio being 0.337 with respect to the offline benchmark. This paper, however, is the first to consider the online benchmark for the edge arrival version of the problem. For this problem, we provide a simple algorithm with an approximation ratio of 0.5 with respect to the online benchmark.

Original languageEnglish (US)
Title of host publicationEC 2022 - Proceedings of the 23rd ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery, Inc
Pages967-985
Number of pages19
ISBN (Electronic)9781450391504
DOIs
StatePublished - Jul 12 2022
Event23rd ACM Conference on Economics and Computation, EC 2022 - Boulder, United States
Duration: Jul 11 2022Jul 15 2022

Publication series

NameEC 2022 - Proceedings of the 23rd ACM Conference on Economics and Computation

Conference

Conference23rd ACM Conference on Economics and Computation, EC 2022
Country/TerritoryUnited States
CityBoulder
Period7/11/227/15/22

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • Economics and Econometrics
  • Computational Mathematics
  • Statistics and Probability

Keywords

  • matching markets
  • online matching
  • stochastic matching

Fingerprint

Dive into the research topics of 'Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark'. Together they form a unique fingerprint.

Cite this