Residential College | false |
Status | 已發表Published |
Fully Online Matching | |
Huang, Zhiyi1; Kang, Ning2; Tang, Zhihao Gavin3; Wu, Xiaowei4; Zhang, Yuhao1; Zhu, Xue1 | |
2020-06 | |
Source Publication | JOURNAL OF THE ACM |
ISSN | 0004-5411 |
Volume | 67Issue: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. |
Keyword | Online Matching Ranking |
DOI | 10.1145/3390890 |
URL | View the original |
Indexed By | SCIE |
Language | 英語English |
WOS Research Area | Computer Science |
WOS Subject | Computer Science, Hardware & Architecture ; Computer Science, Information Systems ; Computer Science, Software Engineering ; Computer Science, Theory & Methods |
WOS ID | WOS:000582594800004 |
Publisher | ASSOC COMPUTING MACHINERY, 2 PENN PLAZA, STE 701, NEW YORK, NY 10121-0701 |
Scopus ID | 2-s2.0-85087162239 |
Fulltext Access | |
Citation statistics | |
Document Type | Journal article |
Collection | University of Macau |
Corresponding Author | Tang, Zhihao Gavin |
Affiliation | 1.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. |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment