Combinatorial Ski Rental and Online Bipartite Matching
© 2020 ACM. 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.
Ec 2020 Proceedings of the 21st Acm Conference on Economics and Computation
Start / End Page
International Standard Book Number 13 (ISBN-13)
Digital Object Identifier (DOI)