20/04/2026
【轉知】專題演講-Michael Zlatin教授(Pomona College)
資財系演講資訊
Speaker: Professor Michael Zlatin (Computer Science at Pomona College)
Time:4/24 (Fri) 11:00am-11:50am
Place: Room 417, Management Building 1, 1001 University Road, Hsinchu, Taiwan
Title: Online Matchings and Beyond: The Power of Water-Filling
Abstract: Many modern algorithmic tasks occur in an "online" setting, in which information is revealed sequentially over time, and a decision-maker must make irrevocable decisions as the situation evolves. A classic example is the Online Bipartite Matching problem (OBM). With applications to matching markets, ridesharing platforms, dating apps, and digital advertising, OBM and its variants are very well-studied, and an optimal (1-1/e)-competitive algorithm is known [Karp, Vazirani, Vazirani '90].
In this talk, I will introduce a generalization of OBM called the Online Submodular Assignment problem. This allows us to capture more complex assignment problems of practical relevance. I will show how "submodular water-levels" can be defined to adapt the water-filling algorithm to the submodular setting, and achieve an optimal (1-1/e)-competitive algorithm for Online SAP as well.
The talk is based on joint work with Daniel Hathcock, Billy Jin, Kalen Patton, and Sherry Sarkar.
Speaker: Professor Michael Zlatin (Computer Science at Pomona College)Time:4/24 (Fri) 11:00am-11:50amPlace: Room 417, Management Building 1, 1001 University Road, Hsinchu, TaiwanTitle: Online Matchings and Beyond: The Power of Water-FillingAbstract: Many modern algorithmic tasks occur in an "online"...