Approximation algorithms are efficient algorithms that find approximate solutions to optimization problems with provable guarantees on the distance of the returned solution to the optimal one. They are used when exact solutions cannot be found in polynomial time due to the P ≠ NP conjecture. These algorithms provide either a multiplicative or additive guarantee on the quality of the returned solution, and require mathematical proof certifying their quality. There is ongoing research to better understand the limits of approximability for certain famous optimization problems.

Carnegie Mellon University

Spring 2022

This course explores the design and analysis of algorithms, algorithmic modelling techniques, and their efficiency. It aims to provide tools for designing and analyzing personal algorithms, using various analytical tools and frameworks. Some advanced topics not commonly covered in textbooks are also taught.

No concepts data

+ 37 more conceptsCarnegie Mellon University

Fall 2018

The course provides a rigorous introduction to the foundations of computer science, improving abstract thinking skills and preparing students to be innovators in the field. Topics include computation, computational complexity, and real-world applications of computational concepts. Prerequisites imply this is an intermediate-level course.

No concepts data

+ 25 more concepts