Edge-weighted Online Stochastic Matching: Beating 1 − 1/ε
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-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 language | English |
---|---|
Title of host publication | Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) |
Number of pages | 10 |
Publisher | SIAM |
Publication date | 2024 |
Pages | 4631-4640 |
DOIs | |
Publication status | Published - 2024 |
Event | 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 - Alexandria, United States Duration: 7 Jan 2024 → 10 Jan 2024 |
Conference
Conference | 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 |
---|---|
Land | United States |
By | Alexandria |
Periode | 07/01/2024 → 10/01/2024 |
Sponsor | ACM 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