Title: Learning-Augmented Algorithms for Online Concave Packing and Convex Covering Problems

Speaker: Asst. Prof. Young-San Lin
Melbourne Business School

Summary:
Learning-augmented algorithms have been extensively studied across the computer science community in the recent years, driven by advances in machine learning predictors, which can provide additional information to augment classical algorithms. Such predictions are especially powerful in the context of online problems, where decisions have to be made without knowledge of the future, and which traditionally exhibits impossibility results bounding the performance of any online algorithm. The study of learning-augmented algorithms thus aims to use external advice prudently, to overcome classical impossibility results when the advice is accurate, and still perform comparably to the state-of-the-art online algorithms even when the advice is inaccurate.

In this paper, we present learning-augmented algorithmic frameworks for two fundamental optimization settings, extending and generalizing prior works. For online packing with concave objectives, we present a simple but overarching strategy that switches between the advice and the state-of-the-art online algorithm. For online covering with convex objectives, we greatly extend primal-dual methods for online convex covering programs by Azar, Buchbinder, Chan, Chen, Cohen, Gupta, Huang, Kang, Nagarajan, Naor, and Panigrahi (FOCS 2016) and previous learning-augmented frameworks for online covering linear programs from the literature, to many new applications. We show that our algorithms break impossibility results when the advice is accurate, while maintaining comparable performance with state-of-the-art classical online algorithms even when the advice is erroneous.

Bio:
Young-San Lin is an Assistant Professor in Operations/Management Science at Melbourne Business School (MBS). He has previously held a postdoctoral position at MBS. He completed his Ph.D. in the Department of Computer Science at Purdue University. His research interests are in the interdisciplinary field of theoretical computer science, economics, and operations research, with a focus on network optimisation, market design, revenue management, resource allocation, and online algorithms. His work has been published in leading journals and conference proceedings, including Operations Research, Naval Research Logistics, Algorithmica, ACM Conference on Economics and Computation, Conference on Web and Internet Economics, Conference on Neural Information Processing Systems, International Conference on Artificial Intelligence and Statistics, International Conference on Approximation Algorithms for Combinatorial Optimization Problems, and the European Symposium on Algorithms.

—

SEMINAR: WED 21 MAY 2025 16:00-17:00 (AEST, Melbourne Time)
ZOOM MEETING ID: 873 1557 5255; PASSWORD: 778635