Optimization problems often involve dealing with uncertainty, which can arise from various sources such as incomplete information, stochastic valuations, and unpredictable interactions. Recent advances provide inspiring algorithms and techniques on contract design, mechanism design, online assignment, online selection, etc., exploring how uncertainty affects the complexity and hardness of optimization problems and investigating the trade-offs between computational efficiency and approximation ratio.
This workshop will foster discussions on some exciting achievements in optimization problems under uncertainty. The presentations will overview leading results and techniques in classic problems including balls in bins, prophet inequality, Pandora box problem, etc. We hope that participants will leave with a deeper understanding of the challenges and opportunities in this field, and with new ideas for tackling these problems in their own research.
Session 1 [9 am - 12 am]
[9:00-9:50] The power of two choices: Beyond greedy strategies [Abstract]
Nikhil Bansal, University of Michigan
[9:50-10:20] Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme [Abstract] [slides]
Hu Fu, Shanghai University of Finance and Economics
[10:20-10:40] Tea Break
[10:40-11:10] Online Load and Graph Balancing for Random Order Inputs [Abstract]
Shi Li, Nanjing University
[11:10-12:00] On the Fundamental Finite Character of Learnability in Supervised Learning with Infinite Labels [Abstract]
Shang-hua Teng, University of Southern California
Session 2 [2 pm - 5:30 pm]
[14:00-14:30] Robust Mechanism Design under Nonlinear Utility [Abstract] [slides]
Zizhuo Wang, The Chinese University of Hong Kong, Shenzhen
[14:30-15:00] When is the Certainty-Equivalent Control Optimal for Online Linear Programming? [Abstract] [slides]
Yilun Chen, The Chinese University of Hong Kong, Shenzhen
[15:00-15:30] Achieving Õ(1/ɛ) Sample Complexity for Constrained Markov Decision Process [Abstract]
Jiashuo Jiang, Hong Kong University of Science and Technology
[15:30-16:00] Tea Break
[16:00-16:30] Algorithms for the Generalized Poset Sorting Problem [Abstract] [slides]
Yuhao Zhang, Shanghai Jiao Tong University
[16:30-17:00] Optimal Robust Contract Design [Abstract] [slides]
Zhihao Tang, Shanghai University of Finance and Economics
[17:00-17:30] Quantile Query Based Prophet Inequality [Abstract] [slides]
Xiaowei Wu, University of Macau