Table of Contents
Algorithms and Uncertainty (24h, 3 ECTS)Course OutlineIn many settings such as routing calls in a network, scheduling jobs in processors, or even trading in the stock market, the decision-maker operates in a status of uncertainty. The objective of the course is to study algorithmic models, techniques, analyses, and approaches that have been developed specifically for dealing with this class of problems. The course is will be focused on the following specific aspects of computation under uncertainty:
The course will focus on the analytical/theoretical analysis of algorithms with uncertainty, but also on concrete applications. Instructor teamLanguage: English by default Related courses within MPRIThe following is a list of courses related to the topics of Algorithms and Uncertainty. (To be updated) Lectures and homeworks (will be updated as course progresses)Tentative schedule: 1. [SA, Sep 19]: Introduction to online computation and competitive analysis. Deterministic paging: Optimality of LDF, k-competitiveness of LRU and a tight lower bound. Randomized paging: Proof of Yao's principle, coupon collector, proof that any randomized algorithm is at least H_k-competitive (topics from Chapters 3 and 4 in [BEY]). Homework 1 2. [CD, Sep 26] Randomized paging algorithm Marking. Deterministic and randomized online bidding. lecture notes Homework 2 3. [CD, Oct 3] Models of data for paging. Algorithms with predictions. Ski rental. lecture notes 1 2 3 Homework 3 4. [SA, Oct 10] Linear programming in online computation. An application to set cover (see paper by Bamas et al). The secretary problem: Section 2 from notes by A. Gupta. Homework 4 5. [SA, Oct 17] Continuing the secretary problem via LPs, up to and including Section 2.1.1 in notes by A. Gupta. For a more detailed exposition, see the paper by Buchbinder et al.. Online matching in the random order model: Section 2 of a paper by Kesselheim et al. Online Steiner trees (notes by Thomas Kesselheim). Homework 5 6. [CD] Pandora's box and Prophet inequalities. Homework 6 7. [SA, Oct 31] Online learning: Majority and Randomized Majority algorithms: notes by T. Kesselheim. Application to Metrical Task Systems: paper by Blum and Burch (we discussed briefly Cor. 1 and Thm 4). 8. [CD] Other models of algorithms with uncertainty. Grading scheme and homework policyGrading scheme: 60% from the final exam, and 40% from weekly homeworks. Homework policy: Homeworks are due at the beginning of class. No late homework will be accepted, except for serious reasons (please notify the instructors in time). You should not collaborate with other students, you should not search the internet for similar problems, and you should not use chatgpt or other AI-assisted tools. If you end up using any material outside notes, you must acknowledge your sources. InternshipsWe will propose internships early in the course. We urge all students who are interested to talk to the instructors as soon as possible. The internships will be related to the topics of research of the instructors and the lectures given in the course, or, more broadly, to the research interests of the instructors. Reading material* [BEY] Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press 1998. Related courses outside of MPRI(to be updated) - Nikhil Bansal's course on “Algorithms and Uncertainty” at TU Eindhoven. - Kamesh Munagala’s course on “Optimization and Decision Making under Uncertainty” at Duke University. - Sebastien Bubeck’s and James Lee’s course on “Competitive analysis via Convex Optimization” at the University of Washington. - Allan Borodin’s course on “Online Algorithms and Other Myopic Algorithms” at the University of Toronto. - Nicole Megow’s course on “Algorithms and Uncertainty” at the University of Bremen. |