Informações sobre o curso
4.8
41 ratings
9 reviews
Approximation algorithms, Part 2 This is the continuation of Approximation algorithms, Part 1. Here you will learn linear programming duality applied to the design of some approximation algorithms, and semidefinite programming applied to Maxcut. By taking the two parts of 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 second of a two-part course on Approximation Algorithms....
Globe

cursos 100% online

Comece imediatamente e aprenda em seu próprio cronograma.
Calendar

Prazos flexíveis

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

Sugerido: 7 hours/week

Aprox. 11 horas restantes
Comment Dots

English

Legendas: English
Globe

cursos 100% online

Comece imediatamente e aprenda em seu próprio cronograma.
Calendar

Prazos flexíveis

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

Sugerido: 7 hours/week

Aprox. 11 horas restantes
Comment Dots

English

Legendas: English

Programa - O que você aprenderá com este curso

1

Seção
Clock
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....
Reading
9 vídeos (Total de 87 min), 11 leituras, 9 testes
Video9 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
Reading11 leituras
Slides10min
Comment10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides-all10min
Quiz8 exercícios práticos
Quiz 16min
Quiz 22min
Quiz 32min
Quiz 44min
Quiz 54min
Quiz 64min
Quiz 72min
Quiz 84min

2

Seção
Clock
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....
Reading
8 vídeos (Total de 73 min), 9 leituras, 9 testes
Video8 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
Reading9 leituras
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides-all10min
Quiz8 exercícios práticos
Quiz 16min
Quiz 24min
Quiz 34min
Quiz 44min
Quiz 54min
Quiz 66min
Quiz 74min
Quiz 86min

3

Seção
Clock
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....
Reading
9 vídeos (Total de 64 min), 10 leituras, 9 testes
Video9 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
Reading10 leituras
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides-all10min
Quiz8 exercícios práticos
Quiz 12min
Quiz 24min
Quiz 34min
Quiz 44min
Quiz 52min
Quiz 62min
Quiz 72min
Quiz 86min

4

Seção
Clock
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....
Reading
11 vídeos (Total de 76 min), 12 leituras, 10 testes
Video11 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
Reading12 leituras
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Slides10min
Sldies10min
Slides10min
Slides-all10min
Comment10min
Quiz9 exercícios práticos
Quiz 14min
Quiz 24min
Quiz 32min
Quiz 42min
Quiz 54min
Quiz 62min
Quiz 72min
Quiz 82min
Quiz 92min

Instrutores

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

Perguntas Frequentes – FAQ

  • Once you enroll for a Certificate, you’ll have access to all videos, quizzes, and programming assignments (if applicable). Peer review assignments can only be submitted and reviewed once your session has begun. If you choose to explore the course without purchasing, you may not be able to access certain assignments.

  • When you purchase a Certificate you get access to all course materials, including graded assignments. Upon completing the course, your electronic Certificate will be added to your Accomplishments page - from there, you can print your Certificate or add it to your LinkedIn profile. If you only want to read and view the course content, you can audit the course for free.

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