Sign inSign in

Approximation algorithm

Algorithms that run in polynomial time and find solutions that are guaranteed to be close to the optimal or satisfy a large fraction of constraints rather than being exact.
as Ryan O'Donnell defines itCarnegie Mellon UniversityThe wording closest to all 9 definitions
Watch it explained

Know first

Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.

Opens up

Concepts that name this one as a prerequisite.

Lecturers

6

Each in their own terms, from the easiest level.

  • Ana Bell

    MIT · Introductory

    An algorithm that finds an acceptable solution within a certain tolerance (epsilon) rather than an exact equality.
    • 2:19Bisection Search and Newton-Raphson
    • 30:21Floats and Approximation Methods
  • Ryan O'Donnell

    Carnegie Mellon University · Undergraduate

    An efficient algorithm that guarantees finding an assignment of at least a certain value when the optimal assignment meets a threshold.
    • 0:41CSP Approximability: Optimization and Certification
    • 29:20Constraint Satisfaction Problems
  • Erik Demaine & Srini Devadas

    MIT · Undergraduate

    Algorithms that can get us within a certain fraction of optimal and run in polynomial time for optimization problems.
    • 8:19Course Overview, Interval Scheduling
  • Brian Yu

    Harvard University · Undergraduate

    Algorithms that try to find a good solution even if they cannot guarantee finding the globally best solution in a feasible amount of time.
    • 6:12:25Harvard CS50’s Artificial Intelligence with Python – Full University Course
  • Srini Devadas

    MIT · Undergraduate

    An algorithm for a problem of size n that finds near-optimal solutions when finding exact optimal solutions is intractable.
    • 3:57Complexity: Approximation Algorithms
  • Amartya Shankha Biswas

    MIT · Undergraduate

    An algorithm that guarantees a solution within a constant factor of the optimal value.
    • 0:53Approximation Algorithms: Traveling Salesman Problem

Lectures that assume it

4

Connections

22

The lectures that define it or assume it, and the concepts next to it.

6 lecturers. Definitions are written by AI from each lecture’s transcript. A time with a play mark starts the lecture at the moment the lecturer says it.