Combinatorial Ski Rental and Online Bipartite Matching
Published
Conference Paper
© 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.
Full Text
Duke Authors
Cited Authors
- Zhang, H; Conitzer, V
Published Date
- July 13, 2020
Published In
- Ec 2020 Proceedings of the 21st Acm Conference on Economics and Computation
Start / End Page
- 879 - 910
International Standard Book Number 13 (ISBN-13)
- 9781450379755
Digital Object Identifier (DOI)
- 10.1145/3391403.3399470
Citation Source
- Scopus