Edge-weighted Online Stochastic Matching: Beating 1 − 1/ε
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Standard
Edge-weighted Online Stochastic Matching : Beating 1 − 1/ε . / Yan, Shuyi.
Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2024. s. 4631-4640.Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Edge-weighted Online Stochastic Matching
T2 - 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
AU - Yan, Shuyi
N1 - Publisher Copyright: Copyright © 2024 by SIAM.
PY - 2024
Y1 - 2024
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85188293298&partnerID=8YFLogxK
U2 - 10.1137/1.9781611977912.165
DO - 10.1137/1.9781611977912.165
M3 - Article in proceedings
AN - SCOPUS:85188293298
SP - 4631
EP - 4640
BT - Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
PB - SIAM
Y2 - 7 January 2024 through 10 January 2024
ER -
ID: 388025321