Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Optimization (24h, 3 ECTS)

Responsible : Spyros Angelopoulos (CNRS and Paris Sorbonne)

Handouts

Instructors

Related Courses

Objective

The 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 decision-making 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 homeworks

Lectures 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 primal-dual 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, Max-Cut, 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]. Non-clairvoyant scheduling [MPT].

Grading scheme, presentations, and homework policy

There 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.

Presentations

1. Fujita, Takahiro, Hatano, Kohei, Takimoto, Eiji, Combinatorial Online Prediction via Metarounding, Algorithmic Learning Theory, 24th International Conference, ALT 2013, Singapore, October 6-9, 2013. Proceedings. 8139, pp.68-82, 2013-08-20. paper

2. Niv Buchbinder, Shahar Chen, Joseph Naor, and Ohad Shamir. Unified algorithms for online learning and competitive analysis. In COLT 2012 - The Twenty-fifth Annual Conference on Learning Theory, pages 5.1–5.18, 2012. paper

3. Naveen Garg, Anupam Gupta, Amit Kumar, Sahil Singla, Non-clairvoyant Precedence Constrained Scheduling, ICALP, 2019. paper

4. S. Golapundi and D. Panigrahi. Online Algorithms for Rent-or-Buy 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 1-1/e. paper

Internship

We 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

  • [Mun2018] Kamesh Munagala. Optimization under Uncertainty: An Introduction through Approximation. Course notes
  • [WS 2011] D. P. Williamson and D.B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011.
  • [V 2004] V. Vazirani Approximation Algorithms, Springer, 2004.
  • [LRS 2011] Lap-Chi Lau, R. Ravi, Mohit Singh. Iterative Methods in Combinatorial Optimization. Cambridge University Press, May 2011. Available online here.
  • [CCPS 1998] W.J.Cook W.H.Cunningham W.R.Pulleyblank A.Schrijver. Combinatorial Optimization
  • [EK] D. Easley, J. Kleinberg, Networks, Crowds, and Markets: Reasoning About a Highly Connected World, book
  • [AM] A. Madry, How to Get Rich (If You Have Good Advice) notes
  • [DPV] S. Dasgupta, C.H. Papadimitriou, U. Vazirani, Algorithms, Mc Graw Hill, 2006 Book
  • [DV] Ch. Dürr, J.-J. Vie, Programmation Efficace Les 128 Algorithmes Qu'Il Faut Avoir Compris et Codés en Python au Cours de sa Vie, Ellipses, 2016
  • [OS] O. Svensson, Multiplicative weight update method for covering LPs notes
  • [MPT] R. Motwani, S. Phillips, E. Torng, Non-clairvoyant scheduling paper
  • [SW] P. Schuurman, G. Woeginger, Approximation schemes–A tutorial survey
  • [BB] A. Blum and C. Burch, On-line Learning and the Metrical Task System Problem paper (you can also search for the journal version of this paper).
  • [BN] N. Buchbinder and J. (Seffi) Naor, The Design of Competitive Online Algorithms via a Primal–Dual Approach survey.
 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA