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

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cours:c-2-24-1 [2019/10/06 17:14]
angelopoulos [Papers]
cours:c-2-24-1 [2019/11/06 16:17] (current)
angelopoulos [Course lectures]
Line 41: Line 41:
  
 [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 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**. 
 ====Homeworks==== ====Homeworks====
  
Line 50: Line 58:
  
 {{:cours:upload:HW4-2-24-1-2019.pdf|Homework 4}} (due on October 14). {{:cours:upload:HW4-2-24-1-2019.pdf|Homework 4}} (due on October 14).
 +
 +{{:cours:upload:HW6-2-24-1-2019.pdf|Homework 5}} (due on October 21).
 +
 +{{:cours:upload:HW7-2-24-1-2019.pdf|Homework 6}} (due on November 8).
 +
 +
 +
 ==== Grading scheme, presentations, and homework policy==== ==== Grading scheme, presentations, and homework policy====
  
Line 66: Line 81:
   * [[https://papers.nips.cc/paper/4990-an-approximate-efficient-lp-solver-for-lp-rounding.pdf|An Approximate, Efficient Solver for LP Rounding]] by Sridhar et al.    * [[https://papers.nips.cc/paper/4990-an-approximate-efficient-lp-solver-for-lp-rounding.pdf|An Approximate, Efficient Solver for LP Rounding]] by Sridhar et al. 
   * [[http://www.cs.uu.nl/research/techreps/repo/CS-1997/1997-39.pdf|Approximation algorithms for facility location problems]] by Shmoys et al.   * [[http://www.cs.uu.nl/research/techreps/repo/CS-1997/1997-39.pdf|Approximation algorithms for facility location problems]] by Shmoys et al.
 +  * [[https://catalog.lib.kyushu-u.ac.jp/opac_download_md/1786655/main.pdf|Online Linear Optimization for Job Scheduling Under Precedence Constraints]] by Takahiro et al. 
 +  * [[https://catalog.lib.kyushu-u.ac.jp/opac_download_md/1786656/main.pdf|Combinatorial Online Predictionvia Metarounding]] by Takahiro et al.  
 +  * [[https://www.microsoft.com/en-us/research/wp-content/uploads/2016/11/2005-Efficient_Algorithms_for_Online_Decision_Problems.pdf|Efficient algorithms for online decision problems]] by Kalai and Vempala. 
 + 
 ==== Internship ==== ==== Internship ====
  
Line 86: Line 104:
    * [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    * [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 [[https://theory.epfl.ch/courses/topicstcs/Lecture112015.pdf | notes ]]    * [OS] O. Svensson, Multiplicative weight update method for covering LPs [[https://theory.epfl.ch/courses/topicstcs/Lecture112015.pdf | notes ]]
 +   * [MPT] R. Motwani, S. Phillips, E. Torng, Non-clairvoyant scheduling [[http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=869EB6ECB1F7A2CBF7C0012A9DF43741?doi=10.1.1.38.1803&rep=rep1&type=pdf | paper]]
 +   * [SW] P. Schuurman, G. Woeginger, Approximation schemes--A tutorial [[https://www.win.tue.nl/~gwoegi/papers/ptas.pdf | survey]]
 +   * [BB]  A. Blum and C. Burch, On-line Learning and the Metrical Task System Problem [[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.2057&rep=rep1&type=pdf|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
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA