CS 599: Approximation Algorithms for NP-hard Problems.

Spring 2000-01

Instructor: Ashish Goel (agoel@cs.usc.edu)

Is a given Boolean formula satisfiable? What is the best way of visiting all the cities on my itinerary? What is the best multicast tree for my network? How should I assign jobs to machines in a load-balanced fashion? Does my optimized code use the smallest number of registers? Where should I place fire stations in Los Angeles to minimize average response time in an emergency? Over the last two decades, a tremendous variety of optimization problems (including all of the above) have been proved to be NP-hard, making it unlikely that we can solve them exactly. Given the importance of these problems and the diversity of the application domains in which they arise, it is important to persist in the face of the difficulty of these problems and find good approximate solutions. This course will offer a gentle introduction to the field of approximation algorithms. The main theme will be the design of an approximation algorithm that is "close" to optimum for a given problem, and occasionally, to discover lower bounds on the best approximation possible. We will also discuss the use of emerging technologies such as DNA and Quantum computation as tools for solving hard problems.

The course is intended to be of interest to graduate students in Computer Science as well as Electrical Engineering, Mathematics, and Computational Biology.

Prerequisite: An algorithms course at USC (CS 570/CS 303 with at least an A-) or elsewhere (with instructor's consent).

Textbook: Approximation Algorithms for NP-hard Problems. Edited by Dorit S. Hochbaum. PWS Publishing Company, 1997.

Note: We are working towards allowing PhD students in Computer Science to use this course to fulfill a theory core/track requirement. Contact the instructor for more details.