Table of Contents
Optimization (24h, 3 ECTS)Responsible : Spyros Angelopoulos (CNRS and Paris Sorbonne) HandoutsInstructors
Related CoursesThe following is a list of courses related to the topics of Algorithms and Complexity. ObjectiveThe objective of this course is to give an overview of the main techniques used in optimization, with emphasis on mathematical programming. For the 2018 offering of this course, the course will focus on decisionmaking aspects of optimization, and in particular, optimization in the presence of uncertainty. We will study topics that cover certain aspects of online optimization, learning, and stochastic optimization. Course lectures[Sep 16] Quick introduction to linear programming and duality [DPV: 7:1, 7:6]. The primaldual scheme. An application to the shortest path problem [WS: 7.3]. [Sep 23] LP rounding for Vertex Cover. The Maximum Value problem. An 8approximation using LProunding. Stochastic matchings. This follows Chapter 1 in [Mun2018] (see references). [Sep 30] A 3approximation for the Maximum Value problem using Lagrangian relaxation. Prophet inequality. This follows chapters 2.1, 2.2 in [Mun2018]. [Oct 7] Submodular functions (sections 3.1, 3.2 in [Mun2018]). Separation oracles and the ellipsoid method (briefly discussed, see, e.g., Section 4.3 in [WS 2011]). a quick introduction to online computation: the ski rental problem. [Oct 14] How to design approximation schemes for scheduling [SW], a sophisticated rounding for the generalized load balancing problem [KT: 11.7], integrality gap, duality and approximability [V: 12]. [Oct 21] Scheduling with precedence constraints, From offline to online [WS], Nonclairvoyant scheduling [MPT], Multiplicative Weights Update Method [AM]. [Oct 28] Application of the Multiplicative Weights Update Method for Solving Covering Linear Programs [OS], Online Learning and the Metrical Task System [BB], The Doubling Method. Final Exam: Monday, November 25, time and place as for the lectures. This is a closed book exam. You are allowed a single A4 page of your notes, one side only. HomeworksHomework 1 (due on September 23). Homework 2 (due on September 30). Homework 3 (due on October 7). Homework 4 (due on October 14). Homework 5 (due on October 21). Homework 6 (due on November 8). Grading scheme, presentations, and homework policyThere will be homeworks (30%), a class presentation (20%) and a final exam (50%). Homework policy: you should not search for solutions on the internet. If, for some reason, you ended up using outside help, you must cite your sources. No collaboration among students is allowed. All homeworks will be due on the beginning of the class. We will not accept late homeworks, except for serious reasons. PapersHere we will add a list of papers for presentation.
InternshipWe will propose internships early in the course offering. We urge all students who are interested to talk with 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. References
