École normale supérieure
Approximation Algorithms Part I
École normale supérieure

Approximation Algorithms Part I

Taught in English

Some content may not be translated

28,933 already enrolled

Course

Gain insight into a topic and learn the fundamentals

Claire Mathieu

Instructor: Claire Mathieu

4.7

(542 reviews)

35 hours to complete
3 weeks at 11 hours a week
Flexible schedule
Learn at your own pace

Details to know

Assessments

34 quizzes

See how employees at top companies are mastering in-demand skills

Placeholder

There are 5 modules in this course

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

What's included

8 videos13 readings7 quizzes1 peer review

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

What's included

7 videos9 readings7 quizzes1 peer review

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

What's included

8 videos10 readings7 quizzes1 peer review

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

What's included

8 videos11 readings8 quizzes1 peer review

This module deepens the understanding of randomized rounding by developing a sophisticated variant and applying it to another basic problem, the Multiway Cut problem. (This is a more advanced module.)

What's included

5 videos8 readings5 quizzes1 peer review

Instructor

Instructor ratings
4.5 (169 ratings)
Claire Mathieu
École normale supérieure
2 Courses31,236 learners

Offered by

Recommended if you're interested in Algorithms

Why people choose Coursera for their career

Felipe M.
Learner since 2018
"To be able to take courses at my own pace and rhythm has been an amazing experience. I can learn whenever it fits my schedule and mood."
Jennifer J.
Learner since 2020
"I directly applied the concepts and skills I learned from my courses to an exciting new project at work."
Larry W.
Learner since 2021
"When I need courses on topics that my university doesn't offer, Coursera is one of the best places to go."
Chaitanya A.
"Learning isn't just about being better at your job: it's so much more than that. Coursera allows me to learn without limits."

Learner reviews

Showing 3 of 542

4.7

542 reviews

  • 5 stars

    75.83%

  • 4 stars

    21.03%

  • 3 stars

    2.21%

  • 2 stars

    0.92%

  • 1 star

    0%

SN
5

Reviewed on Jun 26, 2016

DA
5

Reviewed on Dec 26, 2015

MH
5

Reviewed on May 28, 2020

New to Algorithms? Start here.

Placeholder

Open new doors with Coursera Plus

Unlimited access to 7,000+ world-class courses, hands-on projects, and job-ready certificate programs - all included in your subscription

Advance your career with an online degree

Earn a degree from world-class universities - 100% online

Join over 3,400 global companies that choose Coursera for Business

Upskill your employees to excel in the digital economy

Frequently asked questions