Abstract: In this talk, we discuss a recent trend in the design of online algorithms in which the online algorithm is enhanced with (potentially erroneous) predictions about the input sequence. The goal is to design algorithms with good "consistency" (i.e., the competitive ratio assuming no prediction error) and "robustness" (i.e., the competitive ratio under adversarial error).
The focus of this talk is on the online bin packing problem. We consider the discrete bin packing problem with predictions that concern the frequency of item sizes in the input sequence. We discuss online algorithms with efficient tradeoffs between their consistency and their robustness and whose performance degrades gently as a function of the error in prediction.
Bio: Shahin Kamali is an assistant professor of Computer Science at York University, where he is a member of the Theory of Computing Group. Before joining York University, he was an assistant professor at the University of Manitoba. Previously, Shahin was a postdoctoral associate and an NSERC postdoctoral fellow at the CSAIL lab at MIT. He completed his PhD at the University of Waterloo in 2014.
Shahin has a broad interest in the design, analysis, and limitations of algorithms. He is particularly interested in online problems such as bin packing, paging, list update, and k-Server. His research also spans big-data applications of algorithms in data compression, graph partitioning, and resource allocation in the cloud.
The Data Science Deep Dive is free and open to the public. If you are interested in giving a talk, please email Mohammad Hajiesmaili or Adam Lechowicz. Note that in addition to being a public lecture series, the Data Science Deep Dive is also a seminar (CompSci 692K, Algorithms with Predictions Seminar) that can be taken for credit.