Acerca de este Curso
4.7
121 calificaciones
34 revisiones
Approximation algorithms, Part I How efficiently can you pack objects into a minimum number of boxes? How well can you cluster nodes so as to cheaply separate a network into components around a few centers? These are examples of NP-hard combinatorial optimization problems. It is most likely impossible to solve such problems efficiently, so our aim is to give an approximate solution that can be computed in polynomial time and that at the same time has provable guarantees on its cost relative to the optimum. This course assumes knowledge of a standard undergraduate Algorithms course, and particularly emphasizes algorithms that can be designed using linear programming, a favorite and amazingly successful technique in this area. By taking this course, you will be exposed to a range of problems at the foundations of theoretical computer science, and to powerful design and analysis techniques. Upon completion, you will be able to recognize, when faced with a new combinatorial optimization problem, whether it is close to one of a few known basic problems, and will be able to design linear programming relaxations and use randomized rounding to attempt to solve your own problem. The course content and in particular the homework is of a theoretical nature without any programming assignments. This is the first of a two-part course on Approximation Algorithms....
Globe

Cursos 100 % en línea

Comienza de inmediato y aprende a tu propio ritmo.
Calendar

Fechas límite flexibles

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

Approx. 21 hours to complete

Sugerido: 4 hours/week...
Comment Dots

English

Subtítulos: English...
Globe

Cursos 100 % en línea

Comienza de inmediato y aprende a tu propio ritmo.
Calendar

Fechas límite flexibles

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

Approx. 21 hours to complete

Sugerido: 4 hours/week...
Comment Dots

English

Subtítulos: English...

Programa - Qué aprenderás en este curso

Week
1
Clock
6 horas para completar

Vertex cover and Linear Programming

We introduce the course topic by a typical example of a basic problem, called Vertex Cover, for which we will design and analyze a state-of-the-art approximation algorithm using two basic techniques, called Linear Programming Relaxation and Rounding. It is a simple, elementary application of powerful techniques....
Reading
8 videos (Total: 54 min), 13 readings, 8 quizzes
Video8 videos
Lecture: Definition4m
Lecture: Integer program6m
Lecture: A linear programming relaxation6m
Lecture: Approximation algorithm6m
Lecture: Analysis6m
Lecture: General facts5m
Half integrality (7:35 bug, fixed in pdf slides)10m
Reading13 lecturas
Slides10m
All slides for all chapters of Approx Algs part 110m
Attempt to upload slides in Keynote format10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Practice Exercises10m
PDF version of the peer-graded assignment10m
Half-integrality slides10m
All slides together in one file10m
Quiz7 ejercicios de práctica
Quiz 1: P vs. NP review6m
Quiz 28m
Quiz 34m
Quiz 46m
Quiz 54m
Quiz 64m
Quiz 74m
Week
2
Clock
5 horas para completar

Knapsack and Rounding

This module shows the power of rounding by using it to design a near-optimal solution to another basic problem: the Knapsack problem....
Reading
7 videos (Total: 52 min), 9 readings, 8 quizzes
Video7 videos
Lecture: Greedy algorithm5m
Lecture: Special dynamic program8m
Lecture: General dynamic program8m
Lecture: algorithm6m
Lecture: analysis7m
Lecture: approximation scheme4m
Reading9 lecturas
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Practise Exercises10m
All slides together in one file10m
Quiz7 ejercicios de práctica
Quiz 12m
Quiz 22m
Quiz 34m
Quiz 42m
Quiz 52m
Quiz 62m
Quiz 72m
Week
3
Clock
5 horas para completar

Bin Packing, Linear Programming and Rounding

This module shows the sophistication of rounding by using a clever variant for another basic problem: bin packing. (This is a more advanced module.)...
Reading
8 videos (Total: 74 min), 10 readings, 8 quizzes
Video8 videos
Lecture: a linear program12m
Lecture: small items6m
Lecture: large items, few sizes11m
Large items, many sizes8m
Lecture: large items analysis8m
Lecture: general algorithm7m
Lecture: conclusion6m
Reading10 lecturas
Slides (with typo corrected)10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Practice Exercises10m
All slides together in one file10m
Quiz7 ejercicios de práctica
Quiz 14m
Quiz 26m
Quiz 32m
Quiz 46m
Quiz 54m
Quiz 66m
Quiz 76m
Week
4
Clock
5 horas para completar

Set Cover and Randomized Rounding

This module introduces a simple and powerful variant of rounding, based on probability: randomized rounding. Its power is applied to another basic problem, the Set Cover problem....
Reading
8 videos (Total: 58 min), 11 readings, 9 quizzes
Video8 videos
Lecture: randomized rounding4m
Lecture: cost analysis5m
Lecture: coverage analysis8m
Lecture: iterated algorithm4m
Lecture: stopping time algorithm4m
Lecture: stopping time analysis10m
Lecture:final remarks6m
Reading11 lecturas
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
A reference on this stopping time analysis10m
Practise Exercise10m
All slides together in one file10m
Quiz8 ejercicios de práctica
Quiz 12m
Quiz 22m
Quiz 32m
Quiz 44m
Quiz 52m
Quiz 62m
Quiz 72m
Quiz 84m

Instructor

Acerca de École normale supérieure

L’École normale supérieure (ENS) est un établissement d'enseignement supérieur pour les études prédoctorales et doctorales (graduate school) et un haut lieu de la recherche française. L'ENS offre à 300 nouveaux étudiants et 200 doctorants chaque année une formation de haut niveau, largement pluridisciplinaire, des humanités et sciences sociales aux sciences dures. Régulièrement distinguée au niveau international, l'ENS a formé 10 médailles Fields et 13 prix Nobel....

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.

  • Cuando compras un Certificado, obtienes acceso a todos los materiales del curso, incluidas las tareas calificadas. Una vez que completes el curso, se añadirá tu Certificado electrónico a la página Logros. Desde allí, puedes imprimir tu Certificado o añadirlo a tu perfil de LinkedIn. Si solo quieres leer y visualizar el contenido del curso, puedes participar del curso como oyente sin costo.

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