USI - Email

Archive / INF Seminars / INF_2023_07_28_ChungShou

USI - Email

	From online algorithms to learning-augmented online algorithms

Host: prof. Evanthia Papadopoulou

Friday

28.07

USI East Campus, Sector D, room D0.02

15:00-16:00


	Chung-Shou Liao National Tsing Hua University, Taiwan

*a coffee break and an informal conversation with Prof. Chung-Shou will follow the seminar.

Abstract: In the past three decades, online algorithms have gained a considerable amount of research interest. The concept of online algorithms has been actually applied to a variety of computational models with uncertainty (e.g., online learning), while the only theoretical measure to evaluate the performance of an online algorithm is “competitive ratio”; that is, comparing an online algorithm to an offline optimal adversary. The fundamental question in the field of online algorithms is that: Can we evaluate the quality of an online algorithm in a better way? A new concept, called learning-augmented algorithms, or algorithms with predictions, was proposed to answer the question in 2018. Precisely, the notion exploits the prediction power of popular machine learning models to obtain the robustness guarantees of competitive analysis for online algorithms. In this talk, we first introduce several classical problems as well as their online algorithms. Next, we discuss not only how to devise online algorithms with learning prediction in order to obtain a better theoretical guarantee, but also how to provide a way to look into different performance evaluation beyond the most common worst-case analysis.

Biography: Chung-Shou Liao joined the faculty of Department of Industrial Engineering and Engineering Management, National Tsing Hua University (NTHU) in February 2010. He has served as a full professor since August 2018. Before joining NTHU, he had worked in Algorithms and Computation Laboratory at Institute of Information Science, Academia Sinica for eight years. He obtained his Ph.D. and M.S. degree from Department of Computer Science and Information Engineering, National Taiwan University, and Combinatorial Mathematics group of Department of Applied Mathematics, National Chiao Tung University, respectively. His research mainly focuses on designing efficient algorithms that can be used to solve difficult combinatorial optimization problems from real applications. His lab has developed approximation algorithms with theoretical analysis for well-known hard problems such as online shortest path, facility location, domination, and scheduling and packing problems. Dr. Liao has also extended his study to systems biology. He has designed graph-theoretic algorithms for global alignment between multiple biological networks and conducted comparative analysis across species. Recently, his lab has explored the area of online and dynamic algorithms. Dr. Liao received Outstanding Young Researcher award of IICM (ACM Taiwan) in 2014. He is also a Fulbright Senior Research Scholar for 2018 and 2019. Dr. Liao served as Program Committee Chair of AAAC 2016 (the 9th Annual Meeting of Asian Association for Algorithms and Computation) and ISAAC 2018 (the 29th International Symposium on Algorithms and Computation). He is Board Member of AAAC, Steering Committee Member of ISAAC, and Associate Editor of Journal of Combinatorial Optimization. Dr. Liao is Senior Member of ACM and IEEE.