1,866 recent views

#### 100% online

Start instantly and learn at your own schedule.

#### Approx. 12 hours to complete

Suggested: 9 hours/week...

#### English

Subtitles: English

#### 100% online

Start instantly and learn at your own schedule.

#### Approx. 12 hours to complete

Suggested: 9 hours/week...

#### English

Subtitles: English

### Syllabus - What you will learn from this course

Week
1
6 hours to complete

## 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 videos
Proof of weak duality theorem6m
Changing the form of the LP10m
Complementary slackness5m
Primal-dual algorithms5m
Vertex cover by primal-dual23m
Conclusion3m
Slides10m
Comment10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides-all10m
8 practice exercises
Quiz 16m
Quiz 22m
Quiz 32m
Quiz 44m
Quiz 54m
Quiz 64m
Quiz 72m
Quiz 84m
Week
2
5 hours to complete

## 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 videos
... and its dual4m
Primal-dual algorithm, Part110m
Primal-dual algorithm,Part 212m
Analysis13m
Proof of the main lemma9m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides-all10m
8 practice exercises
Quiz 16m
Quiz 24m
Quiz 34m
Quiz 44m
Quiz 54m
Quiz 66m
Quiz 74m
Quiz 86m
Week
3
5 hours to complete

## 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 videos
A primal-dual algorithm7m
Analyzing the service cost7m
Analyzing the facility opening cost7m
A better algorithm11m
Analysis7m
Conclusion4m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides-all10m
8 practice exercises
Quiz 12m
Quiz 24m
Quiz 34m
Quiz 44m
Quiz 52m
Quiz 62m
Quiz 72m
Quiz 86m
Week
4
6 hours to complete

## 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 videos
...with an integrality gap of almost 210m
Proof of Lemma7m
A rounding algorithm7m
Analysis6m
The end!3m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Sldies10m
Slides10m
Slides-all10m
Comment10m
9 practice exercises
Quiz 14m
Quiz 24m
Quiz 32m
Quiz 42m
Quiz 54m
Quiz 62m
Quiz 72m
Quiz 82m
Quiz 92m
4.8
9 Reviews

### Top reviews from Approximation Algorithms Part II

By APOct 28th 2016

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

By DAMar 1st 2018

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