Informações sobre o curso
2,295 visualizações recentes

100% online

Comece imediatamente e aprenda em seu próprio cronograma.

Prazos flexíveis

Redefinir os prazos de acordo com sua programação.

Aprox. 12 horas para completar

Sugerido: 9 hours/week...

Inglês

Legendas: Inglês

100% online

Comece imediatamente e aprenda em seu próprio cronograma.

Prazos flexíveis

Redefinir os prazos de acordo com sua programação.

Aprox. 12 horas para completar

Sugerido: 9 hours/week...

Inglês

Legendas: Inglês

Programa - O que você aprenderá com este curso

Semana
1
6 horas para concluir

Linear Programming Duality

This module does not study any specific combinatorial optimization problem. Instead, it introduces a central feature of linear programming, duality.

...
9 vídeos ((Total 87 mín.)), 11 leituras, 9 testes
9 videos
Properties of LP duality6min
Geometry of LP duality10min
Proof of weak duality theorem6min
Changing the form of the LP10min
Complementary slackness5min
Primal-dual algorithms5min
Vertex cover by primal-dual23min
Conclusion3min
11 leituras
Slides10min
Comment10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides-all10min
8 exercícios práticos
Quiz 16min
Quiz 22min
Quiz 32min
Quiz 44min
Quiz 54min
Quiz 64min
Quiz 72min
Quiz 84min
Semana
2
5 horas para concluir

Steiner Forest and Primal-Dual Approximation Algorithms

This module uses linear programming duality to design an algorithm for another basic problem, the Steiner forest problem.

...
8 vídeos ((Total 73 mín.)), 9 leituras, 9 testes
8 videos
A special case: Steiner tree12min
LP relaxation for Steiner forest6min
... and its dual4min
Primal-dual algorithm, Part110min
Primal-dual algorithm,Part 212min
Analysis13min
Proof of the main lemma9min
9 leituras
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides-all10min
8 exercícios práticos
Quiz 16min
Quiz 24min
Quiz 34min
Quiz 44min
Quiz 54min
Quiz 66min
Quiz 74min
Quiz 86min
Semana
3
5 horas para concluir

Facility Location and Primal-Dual Approximation Algorithms

This module continues teaching algorithmic applications of linear programming duality by applying it to another basic problem, the facility location problem.

...
9 vídeos ((Total 64 mín.)), 10 leituras, 9 testes
9 videos
A linear programming relaxation4min
...and its dual8min
A primal-dual algorithm7min
Analyzing the service cost7min
Analyzing the facility opening cost7min
A better algorithm11min
Analysis7min
Conclusion4min
10 leituras
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides-all10min
8 exercícios práticos
Quiz 12min
Quiz 24min
Quiz 34min
Quiz 44min
Quiz 52min
Quiz 62min
Quiz 72min
Quiz 86min
Semana
4
6 horas para concluir

Maximum Cut and Semi-Definite Programming

We introduce a generalization of linear programming, semi-definite programming.This module uses semi-definite programming to design an approximation algorithm for another basic problem, the maximum cut problem.

...
11 vídeos ((Total 76 mín.)), 12 leituras, 10 testes
11 videos
A 2-approximation5min
A linear programming relaxation...11min
...with an integrality gap of almost 210min
Proof of Lemma7min
A quadratic programming relaxation4min
General facts about semidefinite programming7min
A rounding algorithm7min
Analysis6min
General facts about MaxCut6min
The end!3min
12 leituras
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Sldies10min
Slides10min
Slides-all10min
Comment10min
9 exercícios práticos
Quiz 14min
Quiz 24min
Quiz 32min
Quiz 42min
Quiz 54min
Quiz 62min
Quiz 72min
Quiz 82min
Quiz 92min
4.8
9 avaliaçõesChevron Right

Principais avaliações do Approximation Algorithms Part II

por APOct 28th 2016

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

por DAMar 1st 2018

I really appreciate your valuable knowledge sharing. This is a perfect course.

Instrutores

Sobre Escola Normal Superior de Paris

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....

Perguntas Frequentes – FAQ

  • Ao se inscrever para um Certificado, você terá acesso a todos os vídeos, testes e tarefas de programação (se aplicável). Tarefas avaliadas pelos colegas apenas podem ser enviadas e avaliadas após o início da sessão. Caso escolha explorar o curso sem adquiri-lo, talvez você não consiga acessar certas tarefas.

Mais dúvidas? Visite o Central de Ajuda ao Aprendiz.