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

Homeworks

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

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.

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.

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