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, Nonclairvoyant scheduling [MPT], Multiplicative Weights Update Method [AM]. 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). 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
