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-2 [2019/09/09 10:19]
durr [Lectures (Tentative Schedule)]
cours:c-2-24-2 [2020/02/12 12:45] (current)
durr [Lectures (Tentative Schedule)]
Line 44: Line 44:
 **8.1.2020**  [Carola] Black-box complexity: lower bounds for selected classes of iterative optimization heuristics **8.1.2020**  [Carola] Black-box complexity: lower bounds for selected classes of iterative optimization heuristics
  
- **15.1.2020** [Christoph] Local search : 2-approximation for scheduling with precedence relations, Schöning’s randomized local search for 3-SAT, local search for k-medianen français: {{:cours:upload:2-24-2-notes-1.pdf|notes 1}}in english [[https://arxiv.org/abs/0809.2554|simpler proof by Gupta and Tangwongsan'2008]]+ **15.1.2020** [Christoph] Maximum leafs Spanning Tree[[https://www.cs.cmu.edu/afs/cs/academic/class/15854-f05/www/scribe/lec05.pdf|Local search]] : 10-approximation, [[https://www.sciencedirect.com/science/article/pii/S0196677498909440|Greedy]]: 3-approximation.
    
 **22.1.2020** [Christoph] degree constrained minimum spanning tree, [[http://www.designofapproxalgs.com/book.pdf|Williamson, Shmoys: The Design of Approximation Algorithms]] page 49, section 2.6 **22.1.2020** [Christoph] degree constrained minimum spanning tree, [[http://www.designofapproxalgs.com/book.pdf|Williamson, Shmoys: The Design of Approximation Algorithms]] page 49, section 2.6
-then page 243, section 9.3. +then page 243, section 9.3. See also the [[https://www.researchgate.net/publication/220779201_Approximating_the_Minimum_Degree_Spanning_Tree_to_Within_One_from_the_Optimal_Degree/link/0fcfd51409f8509065000000/download|original article]].
    
-**29.1.2020** [Christoph] Markov Chain Monte Carlo search.  If needed [[http://web.stanford.edu/class/cs168/l/l13.pdf|introduction]] to Markov and Chebychev inequalitiesMarkov chains [[https://web.stanford.edu/class/cs168/l/l14.pdf|light]]and [[https://www.win.tue.nl/~jkomjath/SPBlecturenotes.pdf|heavy introduction]]. Application to [[https://people.eecs.berkeley.edu/~sinclair/cs294/n8.pdf|lozenge tilings]]+**29.1.2020** [Christoph] local search for k-median and uncapacitated facility locationen français{{:cours:upload:2-24-2-notes-1.pdf|notes 1}}in english [[https://arxiv.org/abs/0809.2554|simpler proof by Gupta and Tangwongsan'2008]]
  
  
 **5.2.2020** (no lecture, deadline for submitting the documentation of the course project/homework) **5.2.2020** (no lecture, deadline for submitting the documentation of the course project/homework)
  
-**12.2.2020** [Carola+Christoph] Project/Homework presentationsdiscussions+**12.2.2020** [Christoph] Schöning’s randomized local search for 3-SAT, and other algorithms for STAT. [[http://gauss.ececs.uc.edu/Courses/c626/reports/chap.pdf|section 4]], [[http://www.cs.yale.edu/homes/spielman/366/schoening.pdf|Daniel Spielman's notes on Uwe Schoening's algorithm]]{{:cours:upload:2-24-2-notessat.pdf|Notes en français}}
    
 **19.2.2020** (no lecture) **19.2.2020** (no lecture)
 
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