À propos de ce cours

3,833 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. 22 heures pour terminer
Anglais
Sous-titres : 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. 22 heures pour terminer
Anglais
Sous-titres : Anglais

Offert par

Logo École normale supérieure

École normale supérieure

Programme du cours : ce que vous apprendrez dans ce cours

Semaine
1

Semaine 1

6 heures pour terminer

Linear Programming Duality

6 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 16 min
Quiz 22 min
Quiz 32 min
Quiz 44 min
Quiz 54 min
Quiz 64 min
Quiz 72 min
Quiz 84 min
Semaine
2

Semaine 2

5 heures pour terminer

Steiner Forest and Primal-Dual Approximation Algorithms

5 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 16 min
Quiz 24 min
Quiz 34 min
Quiz 44 min
Quiz 54 min
Quiz 66 min
Quiz 74 min
Quiz 86 min
Semaine
3

Semaine 3

5 heures pour terminer

Facility Location and Primal-Dual Approximation Algorithms

5 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 12 min
Quiz 24 min
Quiz 34 min
Quiz 44 min
Quiz 52 min
Quiz 62 min
Quiz 72 min
Quiz 86 min
Semaine
4

Semaine 4

6 heures pour terminer

Maximum Cut and Semi-Definite Programming

6 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 14 min
Quiz 24 min
Quiz 32 min
Quiz 42 min
Quiz 54 min
Quiz 62 min
Quiz 72 min
Quiz 82 min
Quiz 92 min

Avis

Meilleurs avis pour APPROXIMATION ALGORITHMS PART II

Voir tous les avis

Foire Aux Questions

  • Access to lectures and assignments depends on your type of enrollment. If you take a course in audit mode, you will be able to see most course materials for free. To access graded assignments and to earn a Certificate, you will need to purchase the Certificate experience, during or after your audit. If you don't see the audit option:

    • The course may not offer an audit option. You can try a Free Trial instead, or apply for Financial Aid.
    • The course may offer 'Full Course, No Certificate' instead. This option lets you see all course materials, submit required assessments, and get a final grade. This also means that you will not be able to purchase a Certificate experience.

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