Edge-weighted Online Stochastic Matching: Beating 1 − 1/ε

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Documents

  • Fulltext

    Accepted author manuscript, 168 KB, PDF document

We study the edge-weighted online stochastic matching problem. Since [6] introduced the online stochastic matching problem and proposed the (1 − 1/ε)-competitive Suggested Matching algorithm, there has been no improvement in the edge-weighted setting. In this paper, we introduce the first algorithm beating the 1 − 1/ε barrier in this setting, achieving a competitive ratio of 0.645. Under the LP proposed by [13], we design an algorithmic preprocessing, dividing all edges into two classes. Then we use different matching strategies to improve the performance on edges in one class in the early stage and on edges in another class in the late stage, while keeping the matching events of different edges highly independent. By balancing them, we finally guarantee the matched probability of every single edge.

Original languageEnglish
Title of host publicationProceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
Number of pages10
PublisherSIAM
Publication date2024
Pages4631-4640
DOIs
Publication statusPublished - 2024
Event35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 - Alexandria, United States
Duration: 7 Jan 202410 Jan 2024

Conference

Conference35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
LandUnited States
ByAlexandria
Periode07/01/202410/01/2024
SponsorACM Special Interest Group on Algorithms and Computation Theory (SIGACT), SIAM Activity Group on Discrete Mathematics

Bibliographical note

Publisher Copyright:
Copyright © 2024 by SIAM.

ID: 388025321