Edge-weighted Online Stochastic Matching: Beating 1 − 1/ε
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- Fulltext
Accepteret manuskript, 168 KB, PDF-dokument
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.
Originalsprog | Engelsk |
---|---|
Titel | Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) |
Antal sider | 10 |
Forlag | SIAM |
Publikationsdato | 2024 |
Sider | 4631-4640 |
DOI | |
Status | Udgivet - 2024 |
Begivenhed | 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 - Alexandria, USA Varighed: 7 jan. 2024 → 10 jan. 2024 |
Konference
Konference | 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 |
---|---|
Land | USA |
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 |
Bibliografisk note
Publisher Copyright:
Copyright © 2024 by SIAM.
ID: 388025321