About this Course
최근 조회 2,525

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 videos (Total 87 min), 11 readings, 9 quizzes
9개의 동영상
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개의 읽기 자료
Slides10m
Comment10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides-all10m
8개 연습문제
Quiz 16m
Quiz 22m
Quiz 32m
Quiz 44m
Quiz 54m
Quiz 64m
Quiz 72m
Quiz 84m
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 videos (Total 73 min), 9 readings, 9 quizzes
8개의 동영상
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개의 읽기 자료
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides-all10m
8개 연습문제
Quiz 16m
Quiz 24m
Quiz 34m
Quiz 44m
Quiz 54m
Quiz 66m
Quiz 74m
Quiz 86m
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 videos (Total 64 min), 10 readings, 9 quizzes
9개의 동영상
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개의 읽기 자료
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides-all10m
8개 연습문제
Quiz 12m
Quiz 24m
Quiz 34m
Quiz 44m
Quiz 52m
Quiz 62m
Quiz 72m
Quiz 86m
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 videos (Total 76 min), 12 readings, 10 quizzes
11개의 동영상
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개의 읽기 자료
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Sldies10m
Slides10m
Slides-all10m
Comment10m
9개 연습문제
Quiz 14m
Quiz 24m
Quiz 32m
Quiz 42m
Quiz 54m
Quiz 62m
Quiz 72m
Quiz 82m
Quiz 92m
4.8
9개의 리뷰Chevron Right

최상위 리뷰

대학: 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....

자주 묻는 질문

  • 강좌에 등록하면 바로 모든 비디오, 테스트 및 프로그래밍 과제(해당하는 경우)에 접근할 수 있습니다. 상호 첨삭 과제는 이 세션이 시작된 경우에만 제출하고 검토할 수 있습니다. 강좌를 구매하지 않고 살펴보기만 하면 특정 과제에 접근하지 못할 수 있습니다.

궁금한 점이 더 있으신가요? 학습자 도움말 센터를 방문해 보세요.