À propos de ce cours

3,892 consultations récentes
100 % en ligne
Commencez dès maintenant et apprenez aux horaires qui vous conviennent.
Dates limites flexibles
Réinitialisez les dates limites selon votre disponibilité.
Approx. 33 heures pour terminer
Anglais
100 % en ligne
Commencez dès maintenant et apprenez aux horaires qui vous conviennent.
Dates limites flexibles
Réinitialisez les dates limites selon votre disponibilité.
Approx. 33 heures pour terminer
Anglais

Offert par

Placeholder

École normale supérieure

Programme du cours : ce que vous apprendrez dans ce cours

Semaine
1

Semaine 1

8 heures pour terminer

Linear Programming Duality

8 heures pour terminer
9 vidéos (Total 87 min), 11 lectures, 9 quiz
9 vidéos
Properties of LP duality6 min
Geometry of LP duality10 min
Proof of weak duality theorem6 min
Changing the form of the LP10 min
Complementary slackness5 min
Primal-dual algorithms5 min
Vertex cover by primal-dual23 min
Conclusion3 min
11 lectures
Slides10 min
Comment10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides-all10 min
8 exercices pour s'entraîner
Quiz 130 min
Quiz 230 min
Quiz 330 min
Quiz 430 min
Quiz 530 min
Quiz 630 min
Quiz 730 min
Quiz 830 min
Semaine
2

Semaine 2

8 heures pour terminer

Steiner Forest and Primal-Dual Approximation Algorithms

8 heures pour terminer
8 vidéos (Total 73 min), 9 lectures, 9 quiz
8 vidéos
A special case: Steiner tree12 min
LP relaxation for Steiner forest6 min
... and its dual4 min
Primal-dual algorithm, Part110 min
Primal-dual algorithm,Part 212 min
Analysis13 min
Proof of the main lemma9 min
9 lectures
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides-all10 min
8 exercices pour s'entraîner
Quiz 130 min
Quiz 230 min
Quiz 330 min
Quiz 430 min
Quiz 530 min
Quiz 630 min
Quiz 730 min
Quiz 830 min
Semaine
3

Semaine 3

8 heures pour terminer

Facility Location and Primal-Dual Approximation Algorithms

8 heures pour terminer
9 vidéos (Total 64 min), 10 lectures, 9 quiz
9 vidéos
A linear programming relaxation4 min
...and its dual8 min
A primal-dual algorithm7 min
Analyzing the service cost7 min
Analyzing the facility opening cost7 min
A better algorithm11 min
Analysis7 min
Conclusion4 min
10 lectures
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides-all10 min
8 exercices pour s'entraîner
Quiz 130 min
Quiz 230 min
Quiz 330 min
Quiz 430 min
Quiz 530 min
Quiz 630 min
Quiz 730 min
Quiz 830 min
Semaine
4

Semaine 4

9 heures pour terminer

Maximum Cut and Semi-Definite Programming

9 heures pour terminer
11 vidéos (Total 76 min), 12 lectures, 10 quiz
11 vidéos
A 2-approximation5 min
A linear programming relaxation...11 min
...with an integrality gap of almost 210 min
Proof of Lemma7 min
A quadratic programming relaxation4 min
General facts about semidefinite programming7 min
A rounding algorithm7 min
Analysis6 min
General facts about MaxCut6 min
The end!3 min
12 lectures
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Slides10 min
Sldies10 min
Slides10 min
Slides-all10 min
Comment10 min
9 exercices pour s'entraîner
Quiz 130 min
Quiz 230 min
Quiz 330 min
Quiz 430 min
Quiz 530 min
Quiz 630 min
Quiz 730 min
Quiz 830 min
Quiz 930 min

Avis

Meilleurs avis pour APPROXIMATION ALGORITHMS PART II

Voir tous les avis

Foire Aux Questions

D'autres questions ? Visitez le Centre d'Aide pour les Etudiants.