This is a graduate level course
on the design and analysis of combinatorial approximation algorithms for
NP-hard optimization problems. The course is tailored for students with a strong
inclination towards theory. However, students interested in networks, computer
vision, computational biology, and other areas could benefit from this course.
Prerequisites: Students are
expected to possess elementary knowledge in graph theory, computational
complexity, linear programming, and the probabilistic method. A few good
sources for such knowledge are listed below under “references.” We will need
just a tiny portion of their content.
Grading policy: The final
grade will be based on grading homework assignments, and a take-home exam.
Tentative syllabus: The course is approximately
equally divided into three sections:
introduction to approximation algorithms and classical results:
optimization, approximation, bounding the optimum, combinatorial bounds,
greedy, local search, rounding, local ratio, dynamic programming.
methods: sampling, randomized rounding, iterative rounding, region
growing, semidefinite relaxations, embeddings, the primal-dual schema,
introduction to hardness of approximation and the PCP theorem.