UM
Residential Collegefalse
Status已發表Published
Fully Online Matching
Huang, Zhiyi1; Kang, Ning2; Tang, Zhihao Gavin3; Wu, Xiaowei4; Zhang, Yuhao1; Zhu, Xue1
2020-06
Source PublicationJOURNAL OF THE ACM
ISSN0004-5411
Volume67Issue:3Pages:17
Abstract

We introduce a fully online model of maximum cardinality matching in which all vertices arrive online. On the arrival of a vertex, its incident edges to previously arrived vertices are revealed. Each vertex has a deadline that is after all its neighbors' arrivals. If a vertex remains unmatched until its deadline, then the algorithm must irrevocably either match it to an unmatched neighbor or leave it unmatched. The model generalizes the existing one-sided online model and is motivated by applications including ride-sharing platforms, real-estate agency, and so on. We show that the Ranking algorithm by Karp et al. (STOC 1990) is 0.5211-competitive in our fully online model for general graphs. Our analysis brings a novel charging mechanic into the randomized primal dual technique by Devanur et al. (SODA 2013), allowing a vertex other than the two endpoints of a matched edge to share the gain. To our knowledge, this is the first analysis of Ranking that beats 0.5 on general graphs in an online matching problem, a first step toward solving the open problem by Karp et al. (STOC 1990) about the optimality of Ranking on general graphs. If the graph is bipartite, then we show a tight competitive ratio ≈0.5671 of Ranking. Finally, we prove that the fully online model is strictly harder than the previous model as no online algorithm can be 0.6317 < 1- 1/e-competitive in our model, even for bipartite graphs.

KeywordOnline Matching Ranking
DOI10.1145/3390890
URLView the original
Indexed BySCIE
Language英語English
WOS Research AreaComputer Science
WOS SubjectComputer Science, Hardware & Architecture ; Computer Science, Information Systems ; Computer Science, Software Engineering ; Computer Science, Theory & Methods
WOS IDWOS:000582594800004
PublisherASSOC COMPUTING MACHINERY, 2 PENN PLAZA, STE 701, NEW YORK, NY 10121-0701
Scopus ID2-s2.0-85087162239
Fulltext Access
Citation statistics
Document TypeJournal article
CollectionUniversity of Macau
Corresponding AuthorTang, Zhihao Gavin
Affiliation1.The University of Hong Kong, China
2.Huawei Noah's Ark Lab, Unit 525-539, Shatin, Hong Kong, Core Building 2, Hong Kong Science Park, Hong Kong
3.Shanghai University of Finance and Economics, Yangpu District, Shanghai, No. 100,Wudong Road, China
4.University of Macau, Avenida da Universidade, Taipa, Macao
Recommended Citation
GB/T 7714
Huang, Zhiyi,Kang, Ning,Tang, Zhihao Gavin,et al. Fully Online Matching[J]. JOURNAL OF THE ACM, 2020, 67(3), 17.
APA Huang, Zhiyi., Kang, Ning., Tang, Zhihao Gavin., Wu, Xiaowei., Zhang, Yuhao., & Zhu, Xue (2020). Fully Online Matching. JOURNAL OF THE ACM, 67(3), 17.
MLA Huang, Zhiyi,et al."Fully Online Matching".JOURNAL OF THE ACM 67.3(2020):17.
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
[Huang, Zhiyi]'s Articles
[Kang, Ning]'s Articles
[Tang, Zhihao Gavin]'s Articles
Baidu academic
Similar articles in Baidu academic
[Huang, Zhiyi]'s Articles
[Kang, Ning]'s Articles
[Tang, Zhihao Gavin]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Huang, Zhiyi]'s Articles
[Kang, Ning]'s Articles
[Tang, Zhihao Gavin]'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.