Offered By

École normale supérieure

About this Course

4.7

121 ratings

•

34 reviews

Approximation algorithms, Part I
How efficiently can you pack objects into a minimum number of boxes? How well can you cluster nodes so as to cheaply separate a network into components around a few centers? These are examples of NP-hard combinatorial optimization problems. It is most likely impossible to solve such problems efficiently, so our aim is to give an approximate solution that can be computed in polynomial time and that at the same time has provable guarantees on its cost relative to the optimum.
This course assumes knowledge of a standard undergraduate Algorithms course, and particularly emphasizes algorithms that can be designed using linear programming, a favorite and amazingly successful technique in this area. By taking 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 first of a two-part course on Approximation Algorithms....

Start instantly and learn at your own schedule.

Reset deadlines in accordance to your schedule.

Suggested: 4 hours/week...

Subtitles: English...

Start instantly and learn at your own schedule.

Reset deadlines in accordance to your schedule.

Suggested: 4 hours/week...

Subtitles: English...

Week

1We introduce the course topic by a typical example of a basic problem, called Vertex Cover, for which we will design and analyze a state-of-the-art approximation algorithm using two basic techniques, called Linear Programming Relaxation and Rounding. It is a simple, elementary application of powerful techniques....

8 videos (Total 54 min), 13 readings, 8 quizzes

Lecture: Definition4m

Lecture: Integer program6m

Lecture: A linear programming relaxation6m

Lecture: Approximation algorithm6m

Lecture: Analysis6m

Lecture: General facts5m

Half integrality (7:35 bug, fixed in pdf slides)10m

Slides10m

All slides for all chapters of Approx Algs part 110m

Attempt to upload slides in Keynote format10m

Slides10m

Slides10m

Slides10m

Slides10m

Slides10m

Slides10m

Practice Exercises10m

PDF version of the peer-graded assignment10m

Half-integrality slides10m

All slides together in one file10m

Quiz 1: P vs. NP review6m

Quiz 28m

Quiz 34m

Quiz 46m

Quiz 54m

Quiz 64m

Quiz 74m

Week

2This module shows the power of rounding by using it to design a near-optimal solution to another basic problem: the Knapsack problem....

7 videos (Total 52 min), 9 readings, 8 quizzes

Lecture: Greedy algorithm5m

Lecture: Special dynamic program8m

Lecture: General dynamic program8m

Lecture: algorithm6m

Lecture: analysis7m

Lecture: approximation scheme4m

Slides10m

Slides10m

Slides10m

Slides10m

Slides10m

Slides10m

Slides10m

Practise Exercises10m

All slides together in one file10m

Quiz 12m

Quiz 22m

Quiz 34m

Quiz 42m

Quiz 52m

Quiz 62m

Quiz 72m

Week

3This module shows the sophistication of rounding by using a clever variant for another basic problem: bin packing. (This is a more advanced module.)...

8 videos (Total 74 min), 10 readings, 8 quizzes

Lecture: a linear program12m

Lecture: small items6m

Lecture: large items, few sizes11m

Large items, many sizes8m

Lecture: large items analysis8m

Lecture: general algorithm7m

Lecture: conclusion6m

Slides (with typo corrected)10m

Slides10m

Slides10m

Slides10m

Slides10m

Slides10m

Slides10m

Slides10m

Practice Exercises10m

All slides together in one file10m

Quiz 14m

Quiz 26m

Quiz 32m

Quiz 46m

Quiz 54m

Quiz 66m

Quiz 76m

Week

4This module introduces a simple and powerful variant of rounding, based on probability: randomized rounding. Its power is applied to another basic problem, the Set Cover problem....

8 videos (Total 58 min), 11 readings, 9 quizzes

Lecture: randomized rounding4m

Lecture: cost analysis5m

Lecture: coverage analysis8m

Lecture: iterated algorithm4m

Lecture: stopping time algorithm4m

Lecture: stopping time analysis10m

Lecture:final remarks6m

Slides10m

Slides10m

Slides10m

Slides10m

Slides10m

Slides10m

Slides10m

Slides10m

A reference on this stopping time analysis10m

Practise Exercise10m

All slides together in one file10m

Quiz 12m

Quiz 22m

Quiz 32m

Quiz 44m

Quiz 52m

Quiz 62m

Quiz 72m

Quiz 84m

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

When will I have access to the lectures and assignments?

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.

What will I get if I purchase the Certificate?

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.

What is the refund policy?

Is financial aid available?

More questions? Visit the Learner Help Center.

Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.