主讲人
Enze Sun The University of Hong Kong 时间 2026年5月12日 星期二 下午 14:00-15:00 地点 学院104会议室
Abstract In this talk, we investigate a fundamental challenge in online decision-making: breaking the classic 0.5 competitive ratio barrier. Central to our approach is a novel structural insight termed "Free-Deterministic Decomposition". This technique allows us to characterize "worst-case" instances by partitioning them into high-value "free" components and robust "deterministic" components, providing a new path to surpass traditional prophet inequality limits. Biography Enze Sun is a Ph.D. student in Computer Science at the University of Hong Kong, where he is advised by Professor Zhiyi Huang. He received his B.S. in 2021 from the ACM Honors Class at Zhiyuan College, Shanghai Jiao Tong University. His research interests lie in theoretical computer science, with a particular focus on algorithms under uncertainty. Specifically, he works on the design and analysis of online algorithms.
We first demonstrate the power of this decomposition in Online Stochastic Matching. By leveraging this structural partition, we design a two-stage algorithm that achieves a competitive ratio significantly beyond 0.5 in polynomial time. Crucially, we prove that this performance guarantee holds even in the demanding Order-Unaware setting, where the algorithm must remain effective without any prior knowledge of the arrival sequence.
Building on this success, we generalize the decomposition framework to establish Combinatorial Philosopher Inequalities. We show that the "Free-Deterministic" paradigm is a versatile toolkit capable of handling complex combinatorial constraints beyond simple matching. This work offers a unified methodology for robust online selection, demonstrating that structural decomposition is the key to overcoming information scarcity and order uncertainty in real-world resource allocation.
