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: - Online algorithms, in which the input is not known ahead of time;
- Regret minimization and online optimization in machine learning; and
- Recently introduced frameworks such as algorithms with predictions, and algorithms with explorable 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)1. [SA, Sep 17] Introduction to online computation. Deterministic and randomized algorithms for the ski rental problem - Section 3 of this survey
- Lecture slides for the second part (Note: we only covered up to “A different approach to randomization”, but may come back to this later).
- Quick introduction to LP duality (see [Vaz], Section 12.1)
- Homework 1 due September 24. Solutions: see Section 2 of this paper
2. [CD, Sep 24] Prophet inequality 3. [CD, Oct 1] Pandora’s box and the secretary problem. 4. [CD, Oct 8] Algorithms with explorable uncertainty. 5. [SA, Oct 15] Stochastic matchings, online matchings, and the Adwords problem. - Homework 5 due October 22. Solutions
- Further material: Lecture by V. Vazirani on the Adwords problem
6. [SA, Oct 22] Extensions of secretary problems. - Secretary problems via linear programming: paper by Buchbinder et al.
- Online bipartite matching in the random order model: paper by Kesselheim et al.
- Homework 6 due October 29. Solutions: see in particular, Section 3.
7. [SA] Advice complexity of online algorithms. Online algorithms with untrusted and noisy advice. - Online knapsack with advice: paper by Böckenhauer et al.
- Paper on Untrusted advice.
- Homework 7 due November 5. Solutions: For the first part, consider an algorithm that accepts the first price that is at least sqrt(M/m). For the second, and more complex part, see Theorem 2 in this paper by Clemente et al.
8. [SA] Learning-augmented online algorithms. - Online computation with ML-advice paper by Purohit et al.
- Noisy advice: paper.
## Grading scheme and homework policyGrading scheme: 50% from the final exam, and 50% 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, and should not search the internet for similar problems. 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* [DPV] S. Dasgupta, C.H. Papadimitriou, U. Vazirani, Algorithms, Mc Graw Hill, 2006 Book * [Vaz] V. Vazirani, Approximation Algorithms, Springer, 2001 Book ## 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. |