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.

Course lectures

[Sep 17] Linear programming (brief intro), duality, simplex [DPV: 7:1, 7:4, 7:6], duality and optimality: shortest path [WS: 7.3].

[Sep 24] Simple rounding for vertex cover, integrality gap, duality and approximability [V: 12], primal-dual for vertex cover, a sophisticated rounding for the generalized load balancing problem [KT: 11.7].

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

[Oct 8] A 3-approximation for the Maximum Value problem using Lagrangian relaxation. Prophet inequality. This follows chapters 2.1, 2.2 in [Mun2018].

[Oct 15] 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]).

[Oct 22] Set cover via dual fitting (section 4.1. in [Mun 2018]). The ski rental problem (see Section 3 in this survey by Buchbinder and Naor, also covered in Chapter 13 in [Mun2018]).

[Oct 29] The Multiplicative Weight Update algorithm [AM] (see also in this survey by Arora et al.). Application to the solution of covering linear programs [OS].

[Nov 5] Online learning and its relation with the Metrical Task System problem (based on this paper by Blum and Burch).

Homeworks

Homework 1 (due on October 8).

Homework 2 (due on October 15).

Homework 3 (due on October 22).

Homework 4 (due on October 29).

Homework 5 (due on November 5).

Homework 6 (due on November 16).

Grading scheme, presentations, and homework policy

There will be homeworks (25%), a class presentation (25%) and a final exam (50%).

The presentations will be done during class on November 12. Please refer to the email for instructions.

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.

The course exam will be on Monday, Nov 19, in the same room as the lectures. The exam is closed-book, but you can bring a single A4-sized page with your notes. You can use only one side of the page.

Papers

Internship

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.

Posted internships:

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
  • [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
 
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