research-article

How to match when all vertices arrive online

Authors:

Zhihao Gavin Tang,

Xue ZhuAuthors Info & Claims

STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

Pages 17 - 29

https://doi.org/10.1145/3188745.3188858

Published: 20 June 2018 Publication History

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, the algorithm must then 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, etc. 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 towards solving the open problem by Karp et al. (STOC 1990) about the optimality of Ranking on general graphs. If the graph is bipartite, we show that the competitive ratio of Ranking is between 0.5541 and 0.5671. 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.

Supplementary Material

MP4 File (1a-2.mp4)

Download
27.30 MB

References

[1]

{ACC + 16} Melika Abolhassani, T.-H. Hubert Chan, Fei Chen, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Hamid Mahini, and Xiaowei Wu. Beating ratio 0.5 for weighted oblivious matching problems. In ESA, volume 57 of LIPIcs, pages 3:1–3:18. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016.

[2]

{ADFS95} Jonathan Aronson, Martin Dyer, Alan Frieze, and Stephen Suen. Randomized greedy matching. ii. Random Struct. Algorithms, 6(1):55–73, January 1995.

[3]

{AGKM11} Gagan Aggarwal, Gagan Goel, Chinmay Karande, and Aranyak Mehta. Online vertex-weighted bipartite matching and single-bid budgeted allocations. In SODA, pages 1253–1264, 2011.

Digital Library

[4]

{BJN07} Niv Buchbinder, Kamal Jain, and Joseph Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In ESA, volume 4698 of Lecture Notes in Computer Science, pages 253–264. Springer, 2007.

Digital Library

[5]

{BM08} Benjamin Birnbaum and Claire Mathieu. On-line bipartite matching made simple. ACM SIGACT News, 39(1):80–87, 2008.

Digital Library

[6]

{BST17} Niv Buchbinder, Danny Segev, and Yevgeny Tkach. Online algorithms for maximum cardinality matching with edge arrivals. In ESA, volume 87 of LIPIcs, pages 22:1–22:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.

[7]

{CCWZ14} T.-H. Hubert Chan, Fei Chen, Xiaowei Wu, and Zhichao Zhao. Ranking on arbitrary graphs: Rematch via continuous lp with monotone and boundary condition constraints. In SODA, pages 1112–1122, 2014.

Digital Library

[8]

{CTV15} Ashish Chiplunkar, Sumedh Tirodkar, and Sundar Vishwanathan. On randomized algorithms for matching in the online preemptive model. In ESA, volume 9294 of Lecture Notes in Computer Science, pages 325–336. Springer, 2015.

[9]

{DJ12} Nikhil R. Devanur and Kamal Jain. Online matching with concave returns. In STOC, pages 137–144. ACM, 2012.

Digital Library

[10]

{DJK13} Nikhil R. Devanur, Kamal Jain, and Robert D. Kleinberg. Randomized primal-dual analysis of RANKING for online bipartite matching. In SODA, pages 101–107. SIAM, 2013.

Digital Library

[11]

{ELSW13} Leah Epstein, Asaf Levin, Danny Segev, and Oren Weimann. Improved bounds for online preemptive matching. In STACS, volume 20 of LIPIcs, pages 389–399. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2013.

[12]

{GM08} Gagan Goel and Aranyak Mehta. Online budgeted matching in random input models with applications to adwords. In SODA, pages 982–991, 2008.

[13]

{KMT11} Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi. Online bipartite matching with unknown distributions. In STOC, pages 587–596, 2011.

Digital Library

[14]

{KVV90} Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. An optimal algorithm for on-line bipartite matching. In STOC, pages 352–358, 1990.

Digital Library

[15]

{McG05} Andrew McGregor. Finding graph matchings in data streams. In APPROXRANDOM, volume 3624 of Lecture Notes in Computer Science, pages 170– 181. Springer, 2005.

Digital Library

[16]

{MSVV07} Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, and Vijay V. Vazirani. Adwords and generalized online matching. J. ACM, 54(5):22, 2007.

Digital Library

[17]

{MY11} Mohammad Mahdian and Qiqi Yan. Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs. In STOC, pages 597–606, 2011.

Digital Library

[18]

{Var11} Ashwinkumar Badanidiyuru Varadaraja. Buyback problem - approximate matroid intersection with cancellation costs. In ICALP (1), volume 6755 of Lecture Notes in Computer Science, pages 379–390. Springer, 2011.

[19]

{WW15} Yajun Wang and Sam Chiu-wai Wong. Two-sided online bipartite matching and vertex cover: Beating the greedy algorithm. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 1070–1081, 2015.

Cited By

Dickerson JSankararaman KSrinivasan AXu PXu Y(2024)Matching Tasks and Workers under Known Arrival Distributions: Online Task Assignment with Two-sided ArrivalsACM Transactions on Economics and Computation10.1145/365202112:2(1-28)Online publication date: 11-Mar-2024
https://dl.acm.org/doi/10.1145/3652021
Jin QLi BCheng YZhao X(2024)Real-time Multi-platform Route Planning in ridesharingExpert Systems with Applications10.1016/j.eswa.2024.124819255(124819)Online publication date: Dec-2024
https://doi.org/10.1016/j.eswa.2024.124819
Mihail MTröbst T(2024)Online Matching with High ProbabilityAlgorithmic Game Theory10.1007/978-3-031-71033-9_2(21-34)Online publication date: 31-Aug-2024
https://doi.org/10.1007/978-3-031-71033-9_2
Show More Cited By

Index Terms

How to match when all vertices arrive online
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals

We introduce a weighted version of the ranking algorithm by Karp et al. (STOC 1990), and we prove a competitive ratio of 0.6534 for the vertex-weighted online bipartite matching problem when online vertices arrive in random order. Our result shows that ...
Nonseparating Cycles Avoiding Specific Vertices

Thomassen proved that every k+3-connected graph G contains an induced cycle C such that G-VC is k-connected, establishing a conjecture of Lovász. In general, one could ask the following question: For any positive integers k,l, does there exist a ...
Boundary vertices in graphs

The distance d(u, v) between two vertices u and v in a nontrivial connected graph G is the length of a shortest u-v path in G. For a vertex v of G, the eccentricity e(v) is the distance between v and a vertex farthest from v. A vertex v of G is a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

June 2018

1332 pages

ISBN:9781450355599

DOI:10.1145/3188745

General Chairs:
Ilias Diakonikolas
University of Southern California, USA
,
David Kempe
University of Southern California, USA
,
Program Chair:
Monika Henzinger
University of Vienna, Austria

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

STOC '18

Sponsor:

SIGACT

STOC '18: Symposium on Theory of Computing

June 25 - 29, 2018

CA, Los Angeles, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

49
Total Citations
View Citations
742
Total Downloads

Downloads (Last 12 months)54
Downloads (Last 6 weeks)4

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dickerson JSankararaman KSrinivasan AXu PXu Y(2024)Matching Tasks and Workers under Known Arrival Distributions: Online Task Assignment with Two-sided ArrivalsACM Transactions on Economics and Computation10.1145/365202112:2(1-28)Online publication date: 11-Mar-2024
https://dl.acm.org/doi/10.1145/3652021
Jin QLi BCheng YZhao X(2024)Real-time Multi-platform Route Planning in ridesharingExpert Systems with Applications10.1016/j.eswa.2024.124819255(124819)Online publication date: Dec-2024
https://doi.org/10.1016/j.eswa.2024.124819
Mihail MTröbst T(2024)Online Matching with High ProbabilityAlgorithmic Game Theory10.1007/978-3-031-71033-9_2(21-34)Online publication date: 31-Aug-2024
https://doi.org/10.1007/978-3-031-71033-9_2
Yan CYan JShen Y(2023)Pricing Shared RidesSSRN Electronic Journal10.2139/ssrn.4551405Online publication date: 2023
https://doi.org/10.2139/ssrn.4551405
Abeliuk AElbassioni KRahwan TCebrian MRahwan I(2023)Price of Anarchy in Algorithmic Matching of Romantic PartnersACM Transactions on Economics and Computation10.1145/362798512:1(1-25)Online publication date: 3-Nov-2023
https://dl.acm.org/doi/10.1145/3627985
Tang ZWu XZhang Y(2023)Towards a Better Understanding of Randomized Greedy MatchingJournal of the ACM10.1145/3614318Online publication date: 6-Oct-2023
https://doi.org/10.1145/3614318
Klinger AMeyer UShehab MFernandez MLi N(2023)Privacy-Preserving Fully Online Matching with DeadlinesProceedings of the Thirteenth ACM Conference on Data and Application Security and Privacy10.1145/3577923.3583654(105-116)Online publication date: 24-Apr-2023
https://dl.acm.org/doi/10.1145/3577923.3583654
Yang YCheng YYang YYuan YWang G(2023)Batch-Based Cooperative Task Assignment in Spatial Crowdsourcing2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00095(1180-1192)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00095
Wu BHan KZhang E(2023)On the task assignment with group fairness for Spatial crowdsourcingScience Talks10.1016/j.sctalk.2023.100227(100227)Online publication date: Apr-2023
https://doi.org/10.1016/j.sctalk.2023.100227
Mertzios GMolter HNiedermeier RZamaraev VZschoche P(2023)Computing Maximum Matchings in Temporal GraphsJournal of Computer and System Sciences10.1016/j.jcss.2023.04.005Online publication date: May-2023
https://doi.org/10.1016/j.jcss.2023.04.005
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents