Online bipartite matching (OBM) captures the fundamental traits of sequential decision making processes in several emerging e-commerce applications, such as display and search engine advertisement, online revenue management and ride-sharing. In OBM, one side of the bipartition is fixed and known in advance, while nodes from the other side appear one at a time and must immediately be matched or discarded. We study the i.i.d. variant of OBM, where appearing nodes are sampled from a known distribution of types, and consider several relaxations of the set of achievable matching probabilities. We perform a polyhedral study with both "static" and time-indexed probabilities, discuss some facet-defining inequalities, and show how several relaxations correspond to intuitive policies.
Joint work with Alfredo Torrico and Shabbir Ahmed.
Alejandro Toriello is Associate Professor in the Stewart School of Industrial and Systems Engineering (ISyE) at Georgia Tech. Prof. Toriello develops models and methods for decision support in supply chain management, logistics and transportation, and conducts theoretical and computational research in related optimization methodologies. His work has optimized problems as varied as the routing of oil tankers, the shipping of cut flowers and the hiring of health care personnel. He teaches logistics courses in ISyE at the undergraduate and graduate levels, is on the editorial board of various academic journals in operations research and transportation, and is a recipient of an NSF CAREER Award. Toriello received his B.S. and Ph.D. in Industrial Engineering from Georgia Tech in 2003 and 2010, respectively.