Residential Collegefalse
Status已發表Published
Fully online matching II: Beating ranking and water-filling
Huang, Zhiyi1; Tang, Zhihao Gavin2; Wu, Xiaowei3; Zhang, Yuhao1
2020-11
Conference Name61st IEEE Annual Symposium on Foundations of Computer Science (FOCS)
Source PublicationProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2020-November
Pages1380-1391
Conference Date2020/11/16-2020/11/19
Conference PlaceDurham, NC, USA
Abstract

Karp, Vazirani, and Vazirani (STOC 1990) initiated the study of online bipartite matching, which has held a central role in online algorithms ever since. Of particular importance are the Ranking algorithm for integral matching and the Water-filling algorithm for fractional matching. Most algorithms in the literature can be viewed as adaptations of these two in the corresponding models. Recently, Huang et al. (SODA 2019, JACM 2020) introduced a more general model called fully online matching, which considers general graphs and allows all vertices to arrive online. They also generalized Ranking and Water-filling to fully online matching and gave some tight analysis: Ranking is Omega approx 0.567-competitive on bipartite graphs where the Omega-constant satisfies Omega e{Omega}=1, and Water-filling is 2-sqrt{2} approx 0.585-competitive on general graphs. We propose fully online matching algorithms strictly better than Ranking and Water-filling. For integral matching on bipartite graphs, we build on the online primal dual analysis of Ranking and Water-filling to design a 0.569-competitive hybrid algorithm called Balanced Ranking. To our knowledge, it is the first integral algorithm in the online matching literature that successfully integrates ideas from Water-filling. For fractional matching on general graphs, we give a 0.592-competitive algorithm called Eager Water-filling, which may match a vertex on its arrival. By contrast, the original Water-filling algorithm always matches vertices at their deadlines. Our result for fractional matching further shows a separation between fully online matching and the general vertex arrival model by Wang and Wong (ICALP 2015), due to an upper bound of 0.5914 in the latter model by Buchbinder, Segev, and Tkach (ESA 2017).

KeywordOnline Matching Ranking Water-filling
DOI10.1109/FOCS46700.2020.00130
URLView the original
Indexed ByCPCI-S
Language英語English
WOS Research AreaComputer Science
WOS SubjectComputer Science, Theory & Methods
WOS IDWOS:000652333400122
Scopus ID2-s2.0-85095536833
Fulltext Access
Citation statistics
Document TypeConference paper
CollectionTHE STATE KEY LABORATORY OF INTERNET OF THINGS FOR SMART CITY (UNIVERSITY OF MACAU)
Corresponding AuthorHuang, Zhiyi
Affiliation1.The University of Hong Kong, Hong Kong
2.Shanghai University of Finance and Economics, China
3.University of Macau, Macao
Recommended Citation
GB/T 7714
Huang, Zhiyi,Tang, Zhihao Gavin,Wu, Xiaowei,et al. Fully online matching II: Beating ranking and water-filling[C], 2020, 1380-1391.
APA Huang, Zhiyi., Tang, Zhihao Gavin., Wu, Xiaowei., & Zhang, Yuhao (2020). Fully online matching II: Beating ranking and water-filling. Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2020-November, 1380-1391.
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
[Tang, Zhihao Gavin]'s Articles
[Wu, Xiaowei]'s Articles
Baidu academic
Similar articles in Baidu academic
[Huang, Zhiyi]'s Articles
[Tang, Zhihao Gavin]'s Articles
[Wu, Xiaowei]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Huang, Zhiyi]'s Articles
[Tang, Zhihao Gavin]'s Articles
[Wu, Xiaowei]'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.