Date/Time
Date(s) - March 24, 2023
10:40 am - 11:30 am
Location
Weil Hall 406
Categories No Categories
Varun Gupta
Date : Friday, March 24, 2023
Mode : In-Person (Join Via Zoom)
Affiliation: University of Chicago
Bio: Visit Page
Title: Greedy Algorithm for Multiway Matching with Bounded Regret
Abstract: We consider a finite horizon online resource allocation/matching problem where the goal of the decision maker is to combine resources (from a finite set of resource types) into feasible configurations. Each configuration is specified by the number of resources consumed of each type and a reward. The resources are further subdivided into three types – offline, online-queueable (which arrive online and can be stored in a buffer), and online-nonqueueable (which arrive online and must be matched on arrival or lost). We prove the efficacy of a simple greedy algorithm when the corresponding static planning linear program (SPP) exhibits a non-degeneracy condition called the general position gap (GPG). In particular we prove that, (i) our greedy algorithm gets bounded any-time regret when no configuration contains both an online-queueable and an online-nonqueueable resource, and (ii) O(log t) expected any-time regret otherwise (we also prove a matching lower bound). By considering the three types of resources, our matching framework encompasses several well-studied problems such as dynamic multi-sided matching, network revenue management, online stochastic packing, and multiclass queueing systems.
Bio: Varun Gupta is an Associate Professor of Operations Management at The University of Chicago Booth School of Business. He obtained his PhD in computer science from Carnegie Mellon University and bachelor’s in computer science and engineering from the Indian Institute of Technology in Delhi. His research interests include stochastic modeling and optimization, applied probability, algorithm design and analysis, and mechanism design. He is particularly interested in modeling and optimization of resource allocation policies for multi-server and distributed systems (e.g., third party logistics, cloud infrastructure, health care) from a queueing theoretic perspective, and learning and control in non-stationary environments. Outside of academia Varun has spent time in industry at Alcatel-Lucent Bell Laboratories, Microsoft Research, Google Research, and is a faculty scholar at Convoy (a 3PL company).