Algorithms with Predictions
Seminar
Basic Information
| Given by: | Kurt Mehlhorn, Nidhi Rathi, Golnoosh Shahkarami |
|---|---|
| Time: | Tuesdays, 2-4pm |
| Room: | 024 (E1 4) |
| First Meeting: | October 22, 2024 |
| Credits: | 7 credit points |
| Prerequisites: | This is a theoretical seminar that will require mathematical maturity (in particular, the ability to understand and write formal mathematical proofs) and a good background in algorithms. A proper preparation of your talk will require non-trivial effort. The target audience of this seminar are master students, PhD students, as well as postdocs. |
| Deadlines: | TBA |
Description
Learning-augmented algorithms is a recent line of research that seeks to blend the strengths of machine learning with classical algorithms, aiming for both practical efficiency and robustness. In this framework, we are provided with predictions about missing data—such as future data in online algorithms or private data in truthful mechanisms—though the accuracy of these predictions is uncertain. The objective is to improve the performance guarantees when predictions are accurate and to incur only a constant loss when predictions are poor.
Some initial lectures will be taken by the instructors to explain the basics that will help students to select their paper/topic. The seminar is open for all interested students and postdocs. Students aiming to get credit points must give a regular presentation (of the chosen research paper) and write a short summary about it. The presentation needs to be discussed with us at least one week before your scheduled talk.
Contact us (nrathi@mpi-inf.mpg.de, gshahkar@mpi-inf.mpg.de) in case there are any questions!
| Papers | Authors |
|---|---|
| A Universal Error Measure for Input Predictions Applied to Online Graph Problems | Giulia Bernardini, Alexander Lindermayr, Alberto Marchetti-Spaccamela, Nicole Megow, Leen Stougie, Michelle Sweering |
| Online metric algorithms with untrusted predictions | Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, Bertrand Simon |
| Online Graph Algorithms with Predictions | Yossi Azar, Debmalya Panigrahi, Noam Touitou |
| Secretary and Online Matching Problems with Machine Learned Advice | Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, Pavel Kolev |
| A Novel Prediction Setup for Online Speed-Scaling | Antonios Antoniadis, Peyman Jabbarzade Ganje, Golnoosh Shahkarami |
| Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location | Priyank Agrawal, Eric Balkanski, Vasilis Gkatzelis, Tingting Ou, Xizhi Tan |
| Mechanism Design with Predictions | Chenyang Xu, Pinyan Lu |
| Strategyproof Scheduling with Predictions | Eric Balkanski, Vasilis Gkatzelis, Xizhi Tan |
| Learning-Augmented Metric Distortion via (p,q)-Veto Core | Ben Berger, Michal Feldman, Vasilis Gkatzelis, Xizhi Tan |
| Incremental Topological Ordering and Cycle Detection with Predictions | Samuel McCauley, Benjamin Moseley, Aidin Niaparast, Shikha Singh |
| Learning Augmented Binary Search Trees | Honghao Lin, Tian Luo, David P. Woodruff |
How to apply?
Application for seminars is possible through the central SIC seminar system (https://seminars.cs.uni-saarland.de/seminars2425).
If you are interested in attending specifically this seminar, we kindly recommend you to
- send a request by e-mail to Nidhi Rathi or Golnoosh Shahkarami. Please indicate your full name and enrollment number.
- apply for this seminar in the central SIC seminar system.