Combinatorial Ski Rental and Online Bipartite Matching


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