Residential College | false |
Status | 已發表Published |
Improved Competitive Ratio for Edge-Weighted Online Stochastic Matching | |
Qiu, Guoliang1; Feng, Yilong2; Zhou, Shengwei2; Wu, Xiaowei2 | |
2024 | |
Conference Name | 19th International Conference on Web and Internet Economics, WINE 2023 |
Source Publication | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
Volume | 14413 |
Pages | 527-544 |
Conference Date | 4-8 December 2023 |
Conference Place | Shanghai |
Publisher | Springer Science and Business Media Deutschland GmbH |
Abstract | We consider the edge-weighted online stochastic matching problem, in which an edge-weighted bipartite graph G= (I∪ J, E) with offline vertices J and online vertex types I is given. The online vertices have types sampled from I with probability proportional to the arrival rates of online vertex types. The online algorithm must make immediate and irrevocable matching decisions with the objective of maximizing the total weight of the matching. For the problem with general arrival rates, Feldman et al. (FOCS 2009) proposed the Suggested Matching algorithm and showed that it achieves a competitive ratio of 1 - 1 /e≈ 0.632. The ratio has recently been improved to 0.645 by Yan (2022), who proposed the Multistage Suggested Matching (MSM) algorithm. In this paper, we propose the Evolving Suggested Matching (ESM) algorithm and show that it achieves a competitive ratio of 0.650. |
Keyword | Online Algorithms Poisson Arrival Stochastic Matching |
DOI | 10.1007/978-3-031-48974-7_30 |
URL | View the original |
Language | 英語English |
Scopus ID | 2-s2.0-85181984111 |
Fulltext Access | |
Citation statistics | |
Document Type | Conference paper |
Collection | THE STATE KEY LABORATORY OF INTERNET OF THINGS FOR SMART CITY (UNIVERSITY OF MACAU) |
Corresponding Author | Qiu, Guoliang; Wu, Xiaowei |
Affiliation | 1.Shanghai Jiao Tong University, Shanghai, China 2.IOTSC, University of Macau, Taipa, China |
Corresponding Author Affilication | University of Macau |
Recommended Citation GB/T 7714 | Qiu, Guoliang,Feng, Yilong,Zhou, Shengwei,et al. Improved Competitive Ratio for Edge-Weighted Online Stochastic Matching[C]:Springer Science and Business Media Deutschland GmbH, 2024, 527-544. |
APA | Qiu, Guoliang., Feng, Yilong., Zhou, Shengwei., & Wu, Xiaowei (2024). Improved Competitive Ratio for Edge-Weighted Online Stochastic Matching. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 14413, 527-544. |
Files in This Item: | There are no files associated with this item. |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment