Об этом курсе
Недавно просмотрено: 2,295

100% онлайн

Начните сейчас и учитесь по собственному графику.

Гибкие сроки

Назначьте сроки сдачи в соответствии со своим графиком.

Прибл. 12 часа на выполнение

Предполагаемая нагрузка: 9 hours/week...

Английский

Субтитры: Английский

100% онлайн

Начните сейчас и учитесь по собственному графику.

Гибкие сроки

Назначьте сроки сдачи в соответствии со своим графиком.

Прибл. 12 часа на выполнение

Предполагаемая нагрузка: 9 hours/week...

Английский

Субтитры: Английский

Программа курса: что вы изучите

Неделя
1
6 ч. на завершение

Linear Programming Duality

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

...
9 видео ((всего 87 мин.)), 11 материалов для самостоятельного изучения, 9 тестов
9 видео
Properties of LP duality6мин
Geometry of LP duality10мин
Proof of weak duality theorem6мин
Changing the form of the LP10мин
Complementary slackness5мин
Primal-dual algorithms5мин
Vertex cover by primal-dual23мин
Conclusion3мин
11 материала для самостоятельного изучения
Slides10мин
Comment10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides-all10мин
8 практического упражнения
Quiz 16мин
Quiz 22мин
Quiz 32мин
Quiz 44мин
Quiz 54мин
Quiz 64мин
Quiz 72мин
Quiz 84мин
Неделя
2
5 ч. на завершение

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 видео ((всего 73 мин.)), 9 материалов для самостоятельного изучения, 9 тестов
8 видео
A special case: Steiner tree12мин
LP relaxation for Steiner forest6мин
... and its dual4мин
Primal-dual algorithm, Part110мин
Primal-dual algorithm,Part 212мин
Analysis13мин
Proof of the main lemma9мин
9 материала для самостоятельного изучения
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides-all10мин
8 практического упражнения
Quiz 16мин
Quiz 24мин
Quiz 34мин
Quiz 44мин
Quiz 54мин
Quiz 66мин
Quiz 74мин
Quiz 86мин
Неделя
3
5 ч. на завершение

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 видео ((всего 64 мин.)), 10 материалов для самостоятельного изучения, 9 тестов
9 видео
A linear programming relaxation4мин
...and its dual8мин
A primal-dual algorithm7мин
Analyzing the service cost7мин
Analyzing the facility opening cost7мин
A better algorithm11мин
Analysis7мин
Conclusion4мин
10 материала для самостоятельного изучения
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides-all10мин
8 практического упражнения
Quiz 12мин
Quiz 24мин
Quiz 34мин
Quiz 44мин
Quiz 52мин
Quiz 62мин
Quiz 72мин
Quiz 86мин
Неделя
4
6 ч. на завершение

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 видео ((всего 76 мин.)), 12 материалов для самостоятельного изучения, 10 тестов
11 видео
Definition5мин
A 2-approximation5мин
A linear programming relaxation...11мин
...with an integrality gap of almost 210мин
Proof of Lemma7мин
A quadratic programming relaxation4мин
General facts about semidefinite programming7мин
A rounding algorithm7мин
Analysis6мин
General facts about MaxCut6мин
The end!3мин
12 материала для самостоятельного изучения
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Sldies10мин
Slides10мин
Slides-all10мин
Comment10мин
9 практического упражнения
Quiz 14мин
Quiz 24мин
Quiz 32мин
Quiz 42мин
Quiz 54мин
Quiz 62мин
Quiz 72мин
Quiz 82мин
Quiz 92мин
4.8
Рецензии: 9Chevron Right

Лучшие отзывы о курсе Approximation Algorithms Part II

автор: APOct 28th 2016

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

автор: DAMar 1st 2018

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

Преподаватели

О Высшая нормальная школа

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

Часто задаваемые вопросы

  • Зарегистрировавшись на сертификацию, вы получите доступ ко всем видео, тестам и заданиям по программированию (если они предусмотрены). Задания по взаимной оценке сокурсниками можно сдавать и проверять только после начала сессии. Если вы проходите курс без оплаты, некоторые задания могут быть недоступны.

Остались вопросы? Посетите Центр поддержки учащихся.