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/10/22 15:41] (current)
bampis [Papers]
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, Non-clairvoyant scheduling [MPT], Multiplicative Weights Update Method [AM].
 ====Homeworks==== ====Homeworks====
  
Line 50: Line 54:
  
 {{: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).
 +
 ==== Grading scheme, presentations, and homework policy==== ==== Grading scheme, presentations, and homework policy====
  
Line 66: Line 73:
   * [[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 97:
    * [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]]
 
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