Residential Collegefalse
Status已發表Published
Improved Competitive Ratio for Edge-Weighted Online Stochastic Matching
Qiu, Guoliang1; Feng, Yilong2; Zhou, Shengwei2; Wu, Xiaowei2
2024
Conference Name19th International Conference on Web and Internet Economics, WINE 2023
Source PublicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14413
Pages527-544
Conference Date4-8 December 2023
Conference PlaceShanghai
PublisherSpringer 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.

KeywordOnline Algorithms Poisson Arrival Stochastic Matching
DOI10.1007/978-3-031-48974-7_30
URLView the original
Language英語English
Scopus ID2-s2.0-85181984111
Fulltext Access
Citation statistics
Document TypeConference paper
CollectionTHE STATE KEY LABORATORY OF INTERNET OF THINGS FOR SMART CITY (UNIVERSITY OF MACAU)
Corresponding AuthorQiu, Guoliang; Wu, Xiaowei
Affiliation1.Shanghai Jiao Tong University, Shanghai, China
2.IOTSC, University of Macau, Taipa, China
Corresponding Author AffilicationUniversity 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.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Qiu, Guoliang]'s Articles
[Feng, Yilong]'s Articles
[Zhou, Shengwei]'s Articles
Baidu academic
Similar articles in Baidu academic
[Qiu, Guoliang]'s Articles
[Feng, Yilong]'s Articles
[Zhou, Shengwei]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Qiu, Guoliang]'s Articles
[Feng, Yilong]'s Articles
[Zhou, Shengwei]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.