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)



Related Courses


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.

Course lectures

[Sep 16] Quick introduction to linear programming and duality [DPV: 7:1, 7:6]. The primal-dual scheme. An application to the shortest path problem [WS: 7.3].

[Sep 23] LP rounding for Vertex Cover. The Maximum Value problem. An 8-approximation using LP-rounding. Stochastic matchings. This follows Chapter 1 in [Mun2018] (see references).

[Sep 30] A 3-approximation 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], Non-clairvoyant 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.


Homework 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 policy

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



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


  • [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).
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA