Combinatorial Ski Rental and Online Bipartite Matching
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.
