LIPIcs.APPROX-RANDOM.2019.7.pdf
- Filesize: 0.66 MB
- 23 pages
Document
Max-Min Greedy Matching
Authors
-
Part of:
Volume:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Randomization and Computation (RANDOM)
Conference: International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-09-17
File
Document Identifiers
Acknowledgements
A substantial part of this work was conducted in Microsoft Research, Herzlyia. We are grateful to Amos Fiat and Sella Nevo for numerous discussions that contributed significantly to the ideas presented in this paper. We also thank Robert Kleinberg for helpful discussions.
Cite AsGet BibTex
Alon Eden, Uriel Feige, and Michal Feldman. Max-Min Greedy Matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.7
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.7
Abstract
A bipartite graph G(U,V;E) that admits a perfect matching is given. One player imposes a permutation pi over V, the other player imposes a permutation sigma over U. In the greedy matching algorithm, vertices of U arrive in order sigma and each vertex is matched to the highest (under pi) yet unmatched neighbor in V (or left unmatched, if all its neighbors are already matched). The obtained matching is maximal, thus matches at least a half of the vertices. The max-min greedy matching problem asks: suppose the first (max) player reveals pi, and the second (min) player responds with the worst possible sigma for pi, does there exist a permutation pi ensuring to match strictly more than a half of the vertices? Can such a permutation be computed in polynomial time?
The main result of this paper is an affirmative answer for these questions: we show that there exists a polytime algorithm to compute pi for which for every sigma at least rho > 0.51 fraction of the vertices of V are matched. We provide additional lower and upper bounds for special families of graphs, including regular and Hamiltonian graphs. Our solution solves an open problem regarding the welfare guarantees attainable by pricing in sequential markets with binary unit-demand valuations.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational pricing and auctions
- Mathematics of computing → Matchings and factors
Keywords
- Online matching
- Pricing mechanism
- Markets
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Allan Borodin, Denis Pankratov, and Amirali Salehi-Abari. On Conceptually Simple Algorithms for Variants of Online Bipartite Matching. In Approximation and Online Algorithms - 15th International Workshop, WAOA 2017, Vienna, Austria, September 7-8, 2017, Revised Selected Papers, pages 253-268, 2017. URL: https://doi.org/10.1007/978-3-319-89441-6_19.
- Miroslav Chlebík and Janka Chlebíková. Approximation hardness of edge dominating set problems. J. Comb. Optim., 11(3):279-290, 2006. URL: https://doi.org/10.1007/s10878-006-7908-0.
- Ilan Reuven Cohen and David Wajc. Randomized Online Matching in Regular Graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 960-979, 2018. URL: https://doi.org/10.1137/1.9781611975031.62.
- Vincent Cohen-Addad, Alon Eden, Michal Feldman, and Amos Fiat. The Invisible Hand of Dynamic Market Pricing. In Proceedings of the 2016 ACM Conference on Economics and Computation, EC '16, Maastricht, The Netherlands, July 24-28, 2016, pages 383-400, 2016. URL: https://doi.org/10.1145/2940716.2940730.
- Paul Dütting, Michal Feldman, Thomas Kesselheim, and Brendan Lucier. Posted Prices, Smoothness, and Combinatorial Prophet Inequalities. CoRR, abs/1612.03161, 2016. URL: http://arxiv.org/abs/1612.03161.
- Tomer Ezra, Michal Feldman, Tim Roughgarden, and Warut Suksompong. Pricing Identical Items. CoRR, abs/1705.06623, 2017. URL: http://arxiv.org/abs/1705.06623.
- Uriel Feige, R. Ravi, and Mohit Singh. Short Tours through Large Linear Forests. In Integer Programming and Combinatorial Optimization - 17th International Conference, IPCO 2014, Bonn, Germany, June 23-25, 2014. Proceedings, pages 273-284, 2014. URL: https://doi.org/10.1007/978-3-319-07557-0_23.
- Michal Feldman, Nick Gravin, and Brendan Lucier. Combinatorial Auctions via Posted Prices. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 123-135, 2015. URL: https://doi.org/10.1137/1.9781611973730.10.
-
David Gale and L. S. Shapley. College Admissions and the Stability of Marriage. American Math. Monthly, 69:9-15, 1962.
- Gagan Goel and Aranyak Mehta. Online Budgeted Matching in Random Input Models with Applications to Adwords. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '08, pages 982-991, Philadelphia, PA, USA, 2008. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1347082.1347189.
- Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi. Online Bipartite Matching with Unknown Distributions. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC '11, pages 587-596, New York, NY, USA, 2011. ACM. URL: https://doi.org/10.1145/1993636.1993715.
- R. M. Karp, U. V. Vazirani, and V. V. Vazirani. An Optimal Algorithm for On-line Bipartite Matching. In Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing, STOC '90, pages 352-358, New York, NY, USA, 1990. ACM. URL: https://doi.org/10.1145/100216.100262.
- Renato Paes Leme and Sam Chiu-wai Wong. Computing Walrasian Equilibria: Fast Algorithms and Structural Properties. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 632-651, 2017. URL: https://doi.org/10.1137/1.9781611974782.42.
- Brendan Lucier. An economic view of prophet inequalities. SIGecom Exchanges, 16(1):24-47, 2017. URL: https://doi.org/10.1145/3144722.3144725.
- Mohammad Mahdian and Qiqi Yan. Online Bipartite Matching with Random Arrivals: An Approach Based on Strongly Factor-revealing LPs. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC '11, pages 597-606, New York, NY, USA, 2011. ACM. URL: https://doi.org/10.1145/1993636.1993716.
- Vahideh H. Manshadi, Shayan Oveis Gharan, and Amin Saberi. Online Stochastic Matching: Online Actions Based on Offline Statistics. Mathematics of Operations Research, 37(4):559-573, 2012. URL: http://www.jstor.org/stable/23358636.
- Aranyak Mehta. Online Matching and Ad Allocation. Foundations and Trends in Theoretical Computer Science, 8(4):265-368, 2013. URL: https://doi.org/10.1561/0400000057.
- Joseph Naor and David Wajc. Near-Optimum Online Ad Allocation for Targeted Advertising. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC '15, Portland, OR, USA, June 15-19, 2015, pages 131-148, 2015. URL: https://doi.org/10.1145/2764468.2764482.