Instructor: Nathan Klein
Syllabus: Link
Lectures: Tuesday and Thursday, 3:30 - 4:45pm in CDS 701
Office Hours: Tuesday 1:30 - 3:30, Thursday 2:30 - 3:30, and by appointment
Prerequisites: Strong undergraduate-level knowledge of algorithms, linear algebra, and probability. Some familiarity with linear programming and at least one of CS 530, 531, or 537 is recommended but not required. Motivated, mathematically mature undergraduate students who have excelled in CS 237 and CS 330 are also welcome.
Grading: Four homework sets (15% each, lowest dropped), scribe one lecture (10%), participation and (very basic) quizzes (15%), and a final project (30%)
Cow: Point set from Mathematica
We will survey a simple but powerful framework for designing approximation algorithms known as "Relax and Round." Given a (possibly NP-Hard) discrete optimization problem, this framework first relaxes it into a polynomial time solvable one over a continuous domain. It then solves this easier problem, whose solution can have fractional coordinates: for example, it could assign a variable to be half true and half false in a SAT formula. Below, in pink is the convex hull of the feasible solutions of a discrete optimization problem. In purple is a relaxation of it.
In the final step, we round this fractional solution (above in blue) to an integer one (above in red). Our goal will be to find a rounding procedure that, like a good translator, finds an integer solution that approximately preserves the key properties of the fractional one such as cost. There are many beautiful methods known for performing this rounding step, which will be our main focus. We will discuss many of them, such as the use of integral polytopes, iterative rounding, iterative relaxation, and independent and dependent randomized rounding. The course will emphasize graph problems as well as results from the past decade with exciting open directions.