Online Bipartite Matching with Applications to Revenue Management
Monday, July 24, 2017 - 8:30am - 9:00am
Online bipartite matching is a fundamental problem in OR and CS with applications such as offering products to customers or allocating jobs to candidates, advertisers to ad slots, or drivers to passengers. These problems can be abstracted as follows: there are fixed resources, which must be allocated on-the-fly, without assuming anything about future demand. In this research, we study a generalization of this problem when each resource could be sold at multiple known prices. We develop new algorithms that achieve a tight competitive ratio under the integral or asymptotic settings. Our algorithms are simple, intuitive and robust and our competitive ratio is provably optimal, for every possible set of prices. Finally, we illustrate the performance of our algorithms with real-world and synthetic data from various retail applications.