A guide to events on our campuses.

Assembly Series

A tradition of convening thought leaders since 1953

McKelvey School of Engineering

Scheduling with Speed Predictions

Friday, December 2 | 11:00 AM - 12:00 PM

Uncas A. Whitaker Hall, 218
6760 Forest Park Pkwy, St. Louis, MO 63105, USA

Clifford Stein

Wai T. Chang Professor of Industrial Engineering and Operations Research

Professor of Computer Science

Interim Director, Data Science Institute

Columbia University

Algorithms with predictions is a recent framework that has been used to overcome pessimistic worst-case bounds in incomplete information settings. In the context of scheduling, very recent work has leveraged machine-learned predictions to design algorithms that achieve improved approximation ratios in settings where the processing times of the jobs are initially unknown. We study the speed-robust scheduling problem where the speeds of the machines, instead of the processing times of the jobs, are unknown and augment this problem with predictions. In this talk, we give an algorithm that simultaneously achieves, for any x < 1, a 1 + x approximation when the predictions are accurate and a 2+ 2/x approximation when the predictions are not accurate. We also study special cases and evaluate our algorithms performance as a function of the error.

Joint work with Eric Balanski, TingTing Ou and Hao-Ting Wei, all at Columbia.

Event Type

Seminar/Colloquia

Schools

McKelvey School of Engineering

Topic

Science & Technology

Department
Computer Science & Engineering
Event Contact

Smaria@wustl.edu

Speaker Information

Clifford Stein  conducts research in the design and analysis of algorithms and in combinatorial optimization. He is particularly interested in the design of algorithms for hard-to-solve problems, arising in areas such as machine learning, large-scale computing and scheduling, and in designing efficient algorithms for manipulating large data. He designs algorithms for a variety of applications ranging from scheduling problems that arise in computer systems to problems that arise in industrial manufacturing facilities to logistics problems such as the management of elevators. He is also the co-author of the popular textbook, Introduction to Algorithms, which has sold over one million copies worldwide. He is a fellow of the Association for Computing Machinery (ACM), was chair of the Steering Committee for the Annual Symposium on Discrete Algorithms, and has received a Career grant and a Sloan Fellowship. He is currently serving as the interim director of Columbia’s Data Science Institute and holds a joint appointment in computer science. Stein received his PhD in computer science from the Massachusetts Institute of Technology (MIT) and his BSE in computer science from Princeton University.

 

 

Subscribe
Google Calendar iCal Outlook

Discussion