Stay Informed:
Baskin Engineering COVID-19 Information and Resources
Campus Roadmap to Recovery
Zoom Links: Zoom Help | Teaching with Zoom | Zoom Quick Guide

From Worst-case Analysis to Algorithms Augmented with Machine-Learned Predictions

Speaker Name: 
Sungjin Im
Speaker Title: 
Associate Professor
Speaker Organization: 
UC Merced
Start Time: 
Monday, March 22, 2021 - 11:00am
End Time: 
Monday, March 22, 2021 - 12:15pm
Via Zoom Link
Daniel Fremont


Traditional algorithmic research has mainly been focused on worst-case guarantees. Although it has discovered numerous algorithmic ideas of fundamental importance, the resulting algorithms don't often perform the best in practice. This is because they are designed to handle all instances equally, including pathological ones that are hardly observed. To bridge this gap, there has been an effort to go beyond worst-case algorithmics. Machine-learning-augmented algorithms is a fascinating and emerging line of work in the beyond-worst-case algorithmics aiming to strengthen traditional algorithms with machine-learned predictions. In this talk, I will present my past work on multidimensional scheduling in the worst-case framework. I will then discuss several challenges arising in machine-learning-augmented algorithms and show how I address them in my recent work. Worst-case algorithms and this new direction will be shown to help each other.  


Sungjin Im is an associate professor at the University of California, Merced, and is currently visiting Google as a visiting scholar. He obtained his BS and MS in computer science at Seoul National University. He received his PhD in computer science from the University of Illinois at Urbana-Champaign in 2012. He was a postdoctoral associate at Duke University before joining UC Merced in 2014. His PhD studies were mainly supported by a Samsung fellowship. He was a co-winner of the Best Student Paper Award at the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010. He is interested in the design and analysis of algorithms and their applications. He has worked on various discrete optimization problems, with an emphasis on resource allocation and scheduling problems. His research encompasses approximation algorithms, online algorithms, scheduling algorithms, combinatorial optimization, game theory, big data algorithms, and learning theory. His research has been supported by NSF grants, including an NSF Career Award.


 Zoom Link:

Event Type: