Sample-Based Online Generalized Assignment Problem with Unknown Poisson Arrivals
Speakers
Zhenzhen Yan
Assistant Professor, School of Physical and Mathematical Sciences, Nanyang Technological University
Dr. Zhenzhen Yan is an assistant professor at School of Physical and Mathematical Sciences, Nanyang Technological University. She joined SPMS since 2018. Before that, she received her PhD in Management Science from the National University of Singapore, and her BSc and MSc in Management Science, Operations Research from the National University of Defense and Technology in China. Her research interests mainly focus on the interplay between optimization and data analytics. Her first line of research is to solve various operations management problems and engineering problems from the distributionally robust perspective, including supply chain design and operations, and healthcare operations. The second line is to develop data-driven optimization approaches with applications to e-commerce operations and resource allocation. Her work has been published in leading operations management journals including Management Science, Operations Research, MSOM and POMS, and top AI conferences including Neurips, UAI and AAAI. Her work has received media coverage in various outlets including the Straits Times and ScienceDaily etc. She currently serves as an Associate Editor of Decision Sciences.
| Date: |
| Friday, 25 August 2023 |
| Time: |
| 10:00 am - 11:30 am |
| Venue: |
|
NUS Business School Mochtar Riady Building BIZ1 03-07 15 Kent Ridge Drive Singapore 119245 (Map) |
Abstract
We study an edge-weighted online stochastic Generalized Assignment Problem with unknown Poisson arrivals. We provide a sample-based multi-phase algorithm by utilizing both pre-existing offline data (named historical data) and sequentially revealed online data. The developed algorithm employs the concept of exploration-exploitation to dynamically learn the arrival rate and optimize the allocation decision. We establish its parametric performance guarantee measured by a competitive ratio. We further provide a guideline on fine tuning the parameters under different sizes of historical data based on the established parametric form. By analyzing a special case which is a classical online weighted matching problem, we also provide a novel insight on how the historical data’s quantity and quality (measured by the number of underrepresented agents in the data) affect the trade-off between exploration and exploitation in online algorithms and their performance. Finally, we demonstrate the effectiveness of our algorithms numerically.