Approximation Algorithms and Complexity
Explore approximation algorithms for NP-hard problems, online algorithms, approximation in P, and other subjects related to approximation algorithms and their limitations. Examine combinatorial algorithms, as well as algorithms based on linear programming and semidefinite programming. Identify the Probabilistically Checkable Proofs (PCP) Theorem, discuss its applications, and prove a weak version of it. Computer Science 388E and 395T (Topic: Approximtn Algorthms/Complexty) may not both be counted. Three lecture hours a week for one semester.
Prerequisites & course information
Explore approximation algorithms for NP-hard problems, online algorithms, approximation in P, and other subjects related to approximation algorithms and their limitations. Examine combinatorial algorithms, as well as algorithms based on linear programming and semidefinite programming. Identify the Probabilistically Checkable Proofs (PCP) Theorem, discuss its applications, and prove a weak version of it. Computer Science 388E and 395T (Topic: Approximtn Algorthms/Complexty) may not both be counted. Three lecture hours a week for one semester.
Sources
- Course catalogue ↗2026-2027