Combinatorial Ski Rental and Online Bipartite Matching
Pages 879 - 910
Abstract
We consider a combinatorial variant of the classical ski rental problem --- which we call combinatorial ski rental --- where multiple resources are available to purchase and to rent, and are demanded online. Moreover, the costs of purchasing and renting are potentially combinatorial. The dual problem of combinatorial ski rental, which we call combinatorial online bipartite matching, generalizes the classical online bipartite matching problem into a form where constraints, induced by both offline and online vertices, can be combinatorial. We give a 2-competitive (resp. e / (e - 1)-competitive) deterministic (resp. randomized) algorithm for combinatorial ski rental, and an e / (e - 1)-competitive algorithm for combinatorial online bipartite matching. All these ratios are optimal given simple lower bounds inherited from the respective well-studied special cases. We also prove information-theoretic impossibility of constant-factor algorithms when any part of our assumptions is considerably relaxed.
References
[1]
Gagan Aggarwal, Gagan Goel, Chinmay Karande, and Aranyak Mehta. 2011. Online vertex-weighted bipartite matching and single-bid budgeted allocations. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 1253--1264.
[2]
Noga Alon, Baruch Awerbuch, and Yossi Azar. 2003. The online set cover problem. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing. ACM, 100--105.
[3]
Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Seffi Naor. 2006. A general approach to online network optimization problems. ACM Transactions on Algorithms (TALG), Vol. 2, 4 (2006), 640--660.
[4]
Baruch Awerbuch and Yossi Azar. 1997. Buy-at-bulk network design. In Proceedings 38th Annual Symposium on Foundations of Computer Science. IEEE, 542--547.
[5]
Yossi Azar, Umang Bhaskar, Lisa Fleischer, and Debmalya Panigrahi. 2013. Online mixed packing and covering. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 85--100.
[6]
Yossi Azar, Niv Buchbinder, TH Hubert Chan, Shahar Chen, Ilan Reuven Cohen, Anupam Gupta, Zhiyi Huang, Ning Kang, Viswanath Nagarajan, Joseph Naor, et al. 2016. Online algorithms for covering and packing problems with convex objectives. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 148--157.
[7]
Nikhil Bansal, Niv Buchbinder, and Joseph Naor. 2010. Towards the randomized k-server conjecture: A primal-dual approach. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 40--55.
[8]
Nikhil Bansal, Niv Buchbinder, and Joseph Seffi Naor. 2008. Randomized competitive algorithms for generalized caching. In Proceedings of the fortieth annual ACM symposium on Theory of computing. ACM, 235--244.
[9]
Nikhil Bansal, Niv Buchbinder, and Joseph Seffi Naor. 2012. A primal-dual randomized algorithm for weighted paging. Journal of the ACM (JACM), Vol. 59, 4 (2012), 19.
[10]
Niv Buchbinder, Kamal Jain, and Joseph Seffi Naor. 2007. Online primal-dual algorithms for maximizing ad-auctions revenue. In European Symposium on Algorithms. Springer, 253--264.
[11]
Niv Buchbinder and Joseph Naor. 2006. Improved bounds for online routing and packing via a primal-dual approach. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06). IEEE, 293--304.
[12]
Niv Buchbinder and Joseph Seffi Naor. 2009. The design of competitive online algorithms via a primal-dual approach. Foundations and Trends® in Theoretical Computer Science, Vol. 3, 2--3 (2009), 93--263.
[13]
TH Hubert Chan, Zhiyi Huang, Shaofeng H-C Jiang, Ning Kang, and Zhihao Gavin Tang. 2017. Online Submodular Maximization with Free Disposal: Randomization Beats for Partition Matroids. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1204--1223.
[14]
Nikhil R Devanur and Thomas P Hayes. 2009. The adwords problem: online keyword matching with budgeted bidders under random permutations. In Proceedings of the 10th ACM conference on Electronic commerce. ACM, 71--78.
[15]
Nikhil R Devanur, Zhiyi Huang, Nitish Korula, Vahab S Mirrokni, and Qiqi Yan. 2016. Whole-page optimization and submodular welfare maximization with online bidders. ACM Transactions on Economics and Computation (TEAC), Vol. 4, 3 (2016), 14.
[16]
Nikhil R Devanur, Kamal Jain, and Robert D Kleinberg. 2013. Randomized primal-dual analysis of ranking for online bipartite matching. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 101--107.
[17]
Daniel R Dooly, Sally A Goldman, and Stephen D Scott. 1998. TCP dynamic acknowledgment delay: theory and practice. In Proceedings of the thirtieth annual ACM symposium on Theory of computing. ACM, 389--398.
[18]
Uriel Feige. 2009. On maximizing welfare when utility functions are subadditive. SIAM J. Comput., Vol. 39, 1 (2009), 122--142.
[19]
Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S Mirrokni, and Cliff Stein. 2010. Online stochastic packing applied to display ad allocation. In European Symposium on Algorithms. Springer, 182--194.
[20]
Jon Feldman, Nitish Korula, Vahab Mirrokni, S Muthukrishnan, and Martin Pál. 2009. Online ad assignment with free disposal. In International workshop on internet and network economics. Springer, 374--385.
[21]
Gagan Goel and Aranyak Mehta. 2008. Online budgeted matching in random input models with applications to adwords. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 982--991.
[22]
Sreenivas Gollapudi and Debmalya Panigrahi. 2019. Online Algorithms for Rent-Or-Buy with Expert Advice. In International Conference on Machine Learning. 2319--2327.
[23]
Elad Hazan and Satyen Kale. 2012. Online submodular minimization. Journal of Machine Learning Research, Vol. 13, Oct (2012), 2903--2922.
[24]
Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang, and Xue Zhu. 2018. How to match when all vertices arrive online. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. ACM, 17--29.
[25]
Zhiyi Huang and Anthony Kim. 2018. Welfare maximization with production costs: A primal dual approach. Games and Economic Behavior (2018).
[26]
Zhiyi Huang, Binghui Peng, Zhihao Gavin Tang, Runzhou Tao, Xiaowei Wu, and Yuhao Zhang. 2019. Tight competitive ratios of classic matching algorithms in the fully online model. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2875--2886.
[27]
Michael Kapralov, Ian Post, and Jan Vondrák. 2013. Online submodular welfare maximization: Greedy is optimal. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms. SIAM, 1216--1225.
[28]
Anna R Karlin, Claire Kenyon, and Dana Randall. 2001. Dynamic TCP acknowledgement and other stories about e/(e-1). In Proceedings of the thirty-third annual ACM symposium on Theory of computing. ACM, 502--509.
[29]
Anna R Karlin, Mark S Manasse, Lyle A McGeoch, and Susan Owicki. 1994. Competitive randomized algorithms for nonuniform problems. Algorithmica, Vol. 11, 6 (1994), 542--571.
[30]
Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani. 1990. An optimal algorithm for on-line bipartite matching. In Proceedings of the twenty-second annual ACM symposium on Theory of computing. ACM, 352--358.
[31]
Zvi Lotker, Boaz Patt-Shamir, and Dror Rawitz. 2012. Rent, lease, or buy: Randomized algorithms for multislope ski rental. SIAM Journal on Discrete Mathematics, Vol. 26, 2 (2012), 718--736.
[32]
Aleksander Madry and Debmalya Panigrahi. 2011. The Semi-stochastic Ski-rental Problem. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
[33]
Aranyak Mehta. 2013. Online matching and ad allocation. Foundations and Trends® in Theoretical Computer Science, Vol. 8, 4 (2013), 265--368.
[34]
Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. 2005. Adwords and generalized on-line matching. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05). IEEE, 264--273.
[35]
Yajun Wang and Sam Chiu-wai Wong. 2015. Two-sided online bipartite matching and vertex cover: Beating the greedy algorithm. In International Colloquium on Automata, Languages, and Programming. Springer, 1070--1081.
[36]
Yajun Wang and Sam Chiu-wai Wong. 2016. Matroid online bipartite matching and vertex cover. In Proceedings of the 2016 ACM Conference on Economics and Computation. ACM, 437--454.
Index Terms
- Combinatorial Ski Rental and Online Bipartite Matching
Recommendations
The multi-shop ski rental problem
SIGMETRICS '14: The 2014 ACM international conference on Measurement and modeling of computer systemsWe consider the multi-shop ski rental problem. This problem generalizes the classic ski rental problem to a multi-shop setting, in which each shop has different prices for renting and purchasing a pair of skis, and a consumer has to make decisions on ...
The multi-shop ski rental problem
Performance evaluation reviewWe consider the multi-shop ski rental problem. This problem generalizes the classic ski rental problem to a multi-shop setting, in which each shop has different prices for renting and purchasing a pair of skis, and a consumer has to make decisions on ...
Non-additive two-option ski rental
We consider the following generalization of the classical problem of ski rental. There is a game that ends at an unknown time, and the algorithm needs to decide how to pay for the time until the game ends. In our generalization, there are two "payment ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2020
937 pages
ISBN:9781450379755
DOI:10.1145/3391403
- General Chairs:
- Péter Biró,
- Jason Hartline,
- Program Chairs:
- Michael Ostrovsky,
- Ariel Procaccia
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 the author(s) 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
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 13 July 2020
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- The National Science Foundation
Conference
EC '20
Sponsor:
EC '20: The 21st ACM Conference on Economics and Computation
July 13 - 17, 2020
Virtual Event, Hungary
Acceptance Rates
Overall Acceptance Rate 664 of 2,389 submissions, 28%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 447Total Downloads
- Downloads (Last 12 months)121
- Downloads (Last 6 weeks)21
Reflects downloads up to 10 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in