题　目：Sample-Based Online Generalized Assignment Problem with Unknown Poisson Arrivals

嘉　宾：王豪，博士，新加坡南洋理工大学

主持人：姚韬，教授，上海交通大学安泰经济与管理学院

时　间：2023年12月8日（周五）9:30-11:45

地　点：安泰经济与管理学院A305

内容简介: We study an online Generalized Assignment Problem with unknown Poisson arrivals. In this model, we consider a bipartite graph that contains offline bins and online items, where each offline bin is associated with a D-dimensional capacity vector and each online item is with a D-dimensional demand vector which may be different towards each bin. Online arrivals are sampled from a set of online item types that follow independent Poisson processes. The arrival rate for each Poisson process is unknown. Each online item will either be packed into an offline bin which will deduct the allocated bin’s capacity vector and generate a reward, or be rejected. The decision should be made immediately and irrevocably upon its arrival. Our goal is to maximize the total reward of the allocation without violating the capacity constraints.

For this problem, we provide a sample-based multi-phase algorithm by utilizing both 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 for fine-tuning the parameters under different historical data based on the established parametric form. By analyzing a special case which is a classical online matching problem, we also provide a novel insight into how the historical data’s quantity and quality affect the trade-off between exploration and exploitation in online algorithms and their performance. Finally, we demonstrate the effectiveness of our algorithms numerically.

演讲人简介：Hao Wang is a postdoc at Nanyang Technological University. Prior to that, he earned his Ph.D. in Mathematics from Nanyang Technological University and obtained a B.E. in Computer Science from Tsinghua University. His research focuses on the intersection of operations research, data science, and computer science. Currently, he is dedicated to addressing online resource allocation problems using data-driven algorithms, particularly in the context of smart city operations, such as ride-sharing and crowd-sourcing. He has published papers in the top journal in operations management POM, the top journal in data sciences TKDE, and the top AI conference AAAI.

欢迎广大师生参加！