Subject:
Combinatorics & Optimization (CO)
Catalog number:
754
Unit weight:
0.50
Meet type:
LEC
Cross-listing(s):
N/A
Requisites:
N/A
Description:
The course studies some of the successful paradigms for designing approximation algorithms and for proving approximation guaranteees, such as the greedy method, formulating and solving linear programming relaxations, the primal-dual method, randomized rounding, semidefinite programming relaxations, approximation of metrics. Also, the PCP theorem, and its application to the hardness of approximating specific problems, e.g., set covering and shortest lattice vector.
Topic titles:
N/A
Faculty:
Mathematics (MAT)
Academic level:
GRD
Course ID:
011797
