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. Lectures and homeworksLectures will continue online (in parentheses the names of the lecturers) [Sept. 21 (EB)] Quick introduction to linear programming and duality [DPV: 7:1, 7:6]. The primaldual scheme [V: 12]. Application to the shortest path problem and the vertex covering. Duality and online computation, the ski rental problem [BN: 3]. [Sept 28 (SA)] Introduction to online computation. Deterministic and randomized algorithms for the ski rental problem (Section 3 of this survey). Homework due October 5. [Oct 5 (SA)] The Set Cover problem. An approximation algorithm using dual fitting (Section 4.1 in [Mun2018]). An application: Conjunctive Query optimization (Section 4.2.1 in [Mun2018]). Online Set Cover (Section 4.4.1 in [BN]). Homework due October 12. [Oct 12 (SA)] Online Selection problems. Prophet inequalities (Section 2.2 in [Mun 2018]). The secretary problem (Section 2 in this survey. Linear programming for secretary problems (mostly Section 2 of this paper by Buchbinder et al). Homework due October 17. [Oct 19 (EB)] Algorithms for Scheduling. List algorithms, approximation schemes [V 2004], from the offline to the online case, generalized load balancing [KT]. [Oct 26 (SA)] Stochastic matchings (Section 1.2 in [Mun 2018]). Online matching via linear programming and the Adwords problem (based on this paper by Devanur, Jain and Kleinberg. Homework due November 2. [Nov 2 (EB)] Introduction to Local Search: Hopfield Neural Networks, MaxCut, Best response dynamics (chapter 12 in [KT]). Introduction to the Multiplicative Weights Update Method (Notes of Aleksander Madry in [Nov 9 (EB)] MWUA for solving covering LPs [OS]. Online learning and the relation with the Metrical Task System [BB]. Nonclairvoyant scheduling [MPT]. Grading scheme, presentations, and homework policyThere will be homeworks, a class presentation, and a final exam. Homework policy: you should *not* search for solutions on the internet. If, for some reason, you used outside help, you must cite your sources. No collaboration among students is allowed. All homeworks will be due at the day and time it is stated in the handout. We will not accept late homeworks, except for serious reasons. Please email each homework to both instructors, in readable pdf. Presentations1. Fujita, Takahiro, Hatano, Kohei, Takimoto, Eiji, Combinatorial Online Prediction via Metarounding, Algorithmic Learning Theory, 24th International Conference, ALT 2013, Singapore, October 69, 2013. Proceedings. 8139, pp.6882, 20130820. paper 2. Niv Buchbinder, Shahar Chen, Joseph Naor, and Ohad Shamir. Unified algorithms for online learning and competitive analysis. In COLT 2012  The Twentyfifth Annual Conference on Learning Theory, pages 5.1–5.18, 2012. paper 3. Naveen Garg, Anupam Gupta, Amit Kumar, Sahil Singla, Nonclairvoyant Precedence Constrained Scheduling, ICALP, 2019. paper 4. S. Golapundi and D. Panigrahi. Online Algorithms for RentorBuy with Expert Advice. paper 5. Antoniadis et al. Online Metric Algorithms with Untrusted Predictions. paper 6. Babaioff et al A Knapsack Secretary Problem with Applications. paper 7. Feldman et al. Online Stochastic Matchings: Beating 11/e. paper InternshipWe 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. References
