【公开学术报告】Sample-Based Online Generalized Assignment Problem with Unknown Poisson Arrivals

Sample-Based Online Generalized Assignment Problem with Unknown Poisson Arrivals

Guest Speaker:      Hao Wang (NTU)

Date & Time:         10:00-11:30 (Beijing Time), Thursday 9th, Nov. 2023

Zoom Meeting:     94747728424（Password: 905819）

Click the Link:       https://zoom.us/j/94747728424

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 into 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.

Key words: Sample-based Algorithm, Online Resource Allocation, Competitive Ratio