About this Course

3,139 recent views
100% online
Start instantly and learn at your own schedule.
Flexible deadlines
Reset deadlines in accordance to your schedule.
Approx. 22 hours to complete
English
Subtitles: English
100% online
Start instantly and learn at your own schedule.
Flexible deadlines
Reset deadlines in accordance to your schedule.
Approx. 22 hours to complete
English
Subtitles: English

Offered by

École normale supérieure logo

École normale supérieure

Syllabus - What you will learn from this course

Week
1

Week 1

6 hours to complete

Linear Programming Duality

6 hours to complete
9 videos (Total 87 min), 11 readings, 9 quizzes
9 videos
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 readings
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

Week 2

5 hours to complete

Steiner Forest and Primal-Dual Approximation Algorithms

5 hours to complete
8 videos (Total 73 min), 9 readings, 9 quizzes
8 videos
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 readings
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

Week 3

5 hours to complete

Facility Location and Primal-Dual Approximation Algorithms

5 hours to complete
9 videos (Total 64 min), 10 readings, 9 quizzes
9 videos
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 readings
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

Week 4

6 hours to complete

Maximum Cut and Semi-Definite Programming

6 hours to complete
11 videos (Total 76 min), 12 readings, 10 quizzes
11 videos
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 readings
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

Reviews

TOP REVIEWS FROM APPROXIMATION ALGORITHMS PART II

View all reviews

Frequently Asked Questions

  • Access to lectures and assignments depends on your type of enrollment. If you take a course in audit mode, you will be able to see most course materials for free. To access graded assignments and to earn a Certificate, you will need to purchase the Certificate experience, during or after your audit. If you don't see the audit option:

    • The course may not offer an audit option. You can try a Free Trial instead, or apply for Financial Aid.
    • The course may offer 'Full Course, No Certificate' instead. This option lets you see all course materials, submit required assessments, and get a final grade. This also means that you will not be able to purchase a Certificate experience.
  • This Course doesn't carry university credit, but some universities may choose to accept Course Certificates for credit. Check with your institution to learn more. Online Degrees and Mastertrack™ Certificates on Coursera provide the opportunity to earn university credit.

More questions? Visit the Learner Help Center.