More Web Proxy on the site http://driver.im/

research-article

Fully Online Matching

Authors:

Zhihao Gavin Tang,

Xue ZhuAuthors Info & Claims

Journal of the ACM (JACM), Volume 67, Issue 3

Article No.: 17, Pages 1 - 25

https://doi.org/10.1145/3390890

Published: 18 May 2020 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, 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.

References

[1]

Melika Abolhassani, T.-H. Hubert Chan, Fei Chen, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Hamid Mahini, and Xiaowei Wu. 2016. Beating ratio 0.5 for weighted oblivious matching problems. In Proceedings of the European Symposium on Algorithms (ESA’16) (LIPIcs), Vol. 57. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 3:1--3:18.

[2]

Gagan Aggarwal, Gagan Goel, Chinmay Karande, and Aranyak Mehta. 2011. Online vertex-weighted bipartite matching and single-bid budgeted allocations. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’11). 1253--1264.

[3]

Jonathan Aronson, Martin Dyer, Alan Frieze, and Stephen Suen. 1995. Randomized greedy matching. II. Random Struct. Algorithms 6, 1 (Jan. 1995), 55--73.

[4]

Itai Ashlagi, Maximilien Burq, Chinmoy Dutta, Patrick Jaillet, Amin Saberi, and Chris Sholley. 2019. Edge weighted online windowed matching. In Proceedings of the ACM Conference on Economics and Computation (EC’19). ACM, 729--742.

Digital Library

[5]

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

Digital Library

[6]

Niv Buchbinder, Kamal Jain, and Joseph Naor. 2007. Online primal-dual algorithms for maximizing ad-auctions revenue. In Proceedings of the European Symposium on Algorithms (ESA’07) (Lecture Notes in Computer Science), Vol. 4698. Springer, 253--264.

[7]

Niv Buchbinder, Danny Segev, and Yevgeny Tkach. 2017. Online algorithms for maximum cardinality matching with edge arrivals. In Proceedings of the European Symposium on Algorithms (ESA’17) (LIPIcs), Vol. 87. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 22:1--22:14.

[8]

T.-H. Hubert Chan, Fei Chen, Xiaowei Wu, and Zhichao Zhao. 2014. Ranking on arbitrary graphs: rematch via continuous LP with monotone and boundary condition constraints. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’14). 1112--1122.

[9]

Ashish Chiplunkar, Sumedh Tirodkar, and Sundar Vishwanathan. 2015. On randomized algorithms for matching in the online preemptive model. In Proceedings of the European Symposium on Algorithms (ESA’15) (Lecture Notes in Computer Science), Vol. 9294. Springer, 325--336.

[10]

Nikhil R. Devanur and Kamal Jain. 2012. Online matching with concave returns. In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC’12). ACM, 137--144.

[11]

Nikhil R. Devanur, Kamal Jain, and Robert D. Kleinberg. 2013. Randomized primal-dual analysis of RANKING for online bipartite matching. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’13). SIAM, 101--107.

Digital Library

[12]

Leah Epstein, Asaf Levin, Danny Segev, and Oren Weimann. 2013. Improved bounds for online preemptive matching. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS’13) (LIPIcs), Vol. 20. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 389--399.

[13]

Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, and David Wajc. 2019. Online matching with general arrivals. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS’19). IEEE Computer Society, 26--37.

[14]

Gagan Goel and Aranyak Mehta. 2008. Online budgeted matching in random input models with applications to adwords. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’08). 982--991.

[15]

Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. 2018. Online vertex-weighted bipartite matching: Beating 1-1/e with random arrivals. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP’18) (LIPIcs), Vol. 107. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 79:1--79:14.

[16]

Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi. 2011. Online bipartite matching with unknown distributions. In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC’11). 587--596.

Digital Library

[17]

Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. 1990. An optimal algorithm for on-line bipartite matching. In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC’90). 352--358.

[18]

Mohammad Mahdian and Qiqi Yan. 2011. Online bipartite matching with random arrivals: An approach based on strongly factor-revealing LPs. In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC’11). 597--606.

Digital Library

[19]

Andrew McGregor. 2005. Finding graph matchings in data streams. In Proceedings of the International Conference on Approximation, Randomization, and Combinatorial Optimization (APPROX-RANDOM’05) (Lecture Notes in Computer Science), Vol. 3624. Springer, 170--181.

Digital Library

[20]

Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, and Vijay V. Vazirani. 2007. AdWords and generalized online matching. J. ACM 54, 5 (2007), 22.

Digital Library

[21]

Matthias Poloczek and Mario Szegedy. 2012. Randomized greedy algorithms for the maximum matching problem with new analysis. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS’12). 708--717.

Digital Library

[22]

Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. 2019. Toward a better understanding of randomized greedy matching. CoRR abs/1907.05135.

[23]

Ashwinkumar Badanidiyuru Varadaraja. 2011. Buyback problem—Approximate matroid intersection with cancellation costs. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP’11) (Lecture Notes in Computer Science), Vol. 6755. Springer, 379--390.

[24]

Yajun Wang and Sam Chiu-wai Wong. 2015. Two-sided online bipartite matching and vertex cover: Beating the greedy algorithm. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP’15). 1070--1081.

Cited By

Huang ZTang ZWajc D(2024)Online Matching: A Brief SurveyACM SIGecom Exchanges10.1145/3699824.369983722:1(135-158)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1145/3699824.3699837
Blikstad JSvensson OVintan RWajc DMohar BShinkar IO'Donnell R(2024)Online Edge Coloring Is (Nearly) as Easy as OfflineProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649741(36-46)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649741
Huang ZZhang QZhang Y(2024)AdWords in a PanoramaSIAM Journal on Computing10.1137/22M147889653:3(701-763)Online publication date: 17-Jun-2024
https://doi.org/10.1137/22M1478896
Show More Cited By

Index Terms

Fully Online Matching
1. Theory of computation
  1. Design and analysis of algorithms
    1. Online algorithms

Recommendations

Periodic Reranking for Online Matching of Reusable Resources
EC '22: Proceedings of the 23rd ACM Conference on Economics and Computation

We consider a generalization of the vertex weighted online bipartite matching problem where the offline vertices, called resources, are reusable. In particular, when a resource is matched it is unavailable for a deterministic time duration d after which ...
Online Matching with High Probability
Algorithmic Game Theory
Abstract
We study the classical, randomized Ranking algorithm, which is known to be $(1 - \frac{1}{e})$ -competitive in expectation for the Online Bipartite Matching Problem. We give a tail inequality bound (Theorem 1), namely that Ranking is $(1 - \frac{1}{e} - α)$ -competitive with ... $^{^{}}$
Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark
EC '22: Proceedings of the 23rd ACM Conference on Economics and Computation

In this paper, we study max-weight stochastic matchings on online bipartite graphs under both vertex and edge arrivals. We focus on designing polynomial time approximation algorithms with respect to the online benchmark, which was first considered by ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 67, Issue 3

Distributed Computing, Parameterized Complexity Theory, Randomized Algorithms, and Computational Geometry

June 2020

189 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/3400020

Editor:
Éva Tardos
Cornell University

Issue’s Table of Contents

Copyright © 2020 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 May 2020

Online AM: 07 May 2020

Accepted: 01 March 2020

Revised: 01 March 2020

Received: 01 July 2019

Published in JACM Volume 67, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Start-up Research Grant of University of Macau
Science and Technology Development Fund, Macau SAR
National Natural Science Foundation of China (NSFC)
Hong Kong Research Grants Council (RGC)

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
1,008
Total Downloads

Downloads (Last 12 months)136
Downloads (Last 6 weeks)17

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Huang ZTang ZWajc D(2024)Online Matching: A Brief SurveyACM SIGecom Exchanges10.1145/3699824.369983722:1(135-158)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1145/3699824.3699837
Blikstad JSvensson OVintan RWajc DMohar BShinkar IO'Donnell R(2024)Online Edge Coloring Is (Nearly) as Easy as OfflineProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649741(36-46)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649741
Huang ZZhang QZhang Y(2024)AdWords in a PanoramaSIAM Journal on Computing10.1137/22M147889653:3(701-763)Online publication date: 17-Jun-2024
https://doi.org/10.1137/22M1478896
Pandya KMaiti A(2024)Randomized ϵ-RANKING Algorithm for Online Trichromatic MatchingIEEE Access10.1109/ACCESS.2024.336779412(28235-28246)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3367794
Tröbst TUdwani R(2024)Almost tight bounds for online hypergraph matchingOperations Research Letters10.1016/j.orl.2024.10714355:COnline publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1016/j.orl.2024.107143
Hosseini HHuang ZIgarashi AShah N(2024)Class fairness in online matchingArtificial Intelligence10.1016/j.artint.2024.104177335(104177)Online publication date: Oct-2024
https://doi.org/10.1016/j.artint.2024.104177
Hosseini HHuang ZIgarashi AShah NWilliams BChen YNeville J(2023)Class fairness in online matchingProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i5.25704(5673-5680)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i5.25704
Li ZWang HYan ZWilliams BChen YNeville J(2023)Fully online matching with stochastic arrivals and departuresProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i10.26417(12014-12021)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i10.26417
Tang ZWu XZhang Y(2023)Toward a Better Understanding of Randomized Greedy MatchingJournal of the ACM10.1145/361431870:6(1-32)Online publication date: 6-Oct-2023
https://dl.acm.org/doi/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
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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents