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

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfæ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.

OriginalsprogEngelsk
TitelProceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
Antal sider10
ForlagSIAM
Publikationsdato2024
Sider4631-4640
DOI
StatusUdgivet - 2024
Begivenhed35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 - Alexandria, USA
Varighed: 7 jan. 202410 jan. 2024

Konference

Konference35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
LandUSA
ByAlexandria
Periode07/01/202410/01/2024
SponsorACM 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