Acerca de este Curso

3,422 vistas recientes

100 % en línea

Comienza de inmediato y aprende a tu propio ritmo.

Fechas límite flexibles

Restablece las fechas límite en función de tus horarios.

Aprox. 13 horas para completar

Sugerido: 10 hours/week...

Inglés (English)

Subtítulos: Inglés (English)

100 % en línea

Comienza de inmediato y aprende a tu propio ritmo.

Fechas límite flexibles

Restablece las fechas límite en función de tus horarios.

Aprox. 13 horas para completar

Sugerido: 10 hours/week...

Inglés (English)

Subtítulos: Inglés (English)

Instructor

Imagen del instructor, Claire Mathieu

Claire Mathieu 

21,058 alumnos
2 cursos

ofrecido por

Logotipo de École normale supérieure

École normale supérieure

Programa - Qué aprenderás en este curso

Semana
1

Semana 1

6 horas para completar

Linear Programming Duality

6 horas para completar
9 videos (Total 87 minutos), 11 lecturas, 9 cuestionarios
9 videos
Properties of LP duality6m
Geometry of LP duality10m
Proof of weak duality theorem6m
Changing the form of the LP10m
Complementary slackness5m
Primal-dual algorithms5m
Vertex cover by primal-dual23m
Conclusion3m
11 lecturas
Slides10m
Comment10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides-all10m
8 ejercicios de práctica
Quiz 16m
Quiz 22m
Quiz 32m
Quiz 44m
Quiz 54m
Quiz 64m
Quiz 72m
Quiz 84m
Semana
2

Semana 2

5 horas para completar

Steiner Forest and Primal-Dual Approximation Algorithms

5 horas para completar
8 videos (Total 73 minutos), 9 lecturas, 9 cuestionarios
8 videos
A special case: Steiner tree12m
LP relaxation for Steiner forest6m
... and its dual4m
Primal-dual algorithm, Part110m
Primal-dual algorithm,Part 212m
Analysis13m
Proof of the main lemma9m
9 lecturas
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides-all10m
8 ejercicios de práctica
Quiz 16m
Quiz 24m
Quiz 34m
Quiz 44m
Quiz 54m
Quiz 66m
Quiz 74m
Quiz 86m
Semana
3

Semana 3

5 horas para completar

Facility Location and Primal-Dual Approximation Algorithms

5 horas para completar
9 videos (Total 64 minutos), 10 lecturas, 9 cuestionarios
9 videos
A linear programming relaxation4m
...and its dual8m
A primal-dual algorithm7m
Analyzing the service cost7m
Analyzing the facility opening cost7m
A better algorithm11m
Analysis7m
Conclusion4m
10 lecturas
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides-all10m
8 ejercicios de práctica
Quiz 12m
Quiz 24m
Quiz 34m
Quiz 44m
Quiz 52m
Quiz 62m
Quiz 72m
Quiz 86m
Semana
4

Semana 4

6 horas para completar

Maximum Cut and Semi-Definite Programming

6 horas para completar
11 videos (Total 76 minutos), 12 lecturas, 10 cuestionarios
11 videos
A 2-approximation5m
A linear programming relaxation...11m
...with an integrality gap of almost 210m
Proof of Lemma7m
A quadratic programming relaxation4m
General facts about semidefinite programming7m
A rounding algorithm7m
Analysis6m
General facts about MaxCut6m
The end!3m
12 lecturas
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Sldies10m
Slides10m
Slides-all10m
Comment10m
9 ejercicios de práctica
Quiz 14m
Quiz 24m
Quiz 32m
Quiz 42m
Quiz 54m
Quiz 62m
Quiz 72m
Quiz 82m
Quiz 92m
4.8
9 revisionesChevron Right

Principales revisiones sobre Approximation Algorithms Part II

por RAMar 14th 2016

It is remarkable to note that Professor Claire Mathieu explains such a complex subject in such a elegant and understandable manner.

por APOct 28th 2016

Demanding course with lots of great algorithm concepts based on Linear Programming.

Preguntas Frecuentes

  • Una vez que te inscribes para obtener un Certificado, tendrás acceso a todos los videos, cuestionarios y tareas de programación (si corresponde). Las tareas calificadas por compañeros solo pueden enviarse y revisarse una vez que haya comenzado tu sesión. Si eliges explorar el curso sin comprarlo, es posible que no puedas acceder a determinadas tareas.

¿Tienes más preguntas? Visita el Centro de Ayuda al Alumno.