Approximation Algorithms

Computer Science 6966/4966
Spring 2010

Instructor: Elliot Anshelevich
311 Lally Hall, 518-276-6491
first letter of first name + first 6 letters of last name AT cs dot rpi dot edu

Time and Place: Tuesdays and Fridays, 12:00pm-1:20pm, Location TBD
Office Hours: TBD

Course Overview

Algorithms with provable guarantees on the quality of their solutions are a powerful way of dealing with intractable problems. This course is an advanced course in approximation algorithms; it will cover fundamental techniques for designing approximation algorithms as well as more specialized topics. Possible topics include: semi-definite and linear programming, inapproximability and the PCP theorem, iterated rounding, metrics and cuts, primal-dual methods, online algorithms, and the unique games conjecture. We will look at algorithms in a variety of settings; some of these may include social networks, graph partitioning, network design and routing, traveling salesman problems, and many applications in communication networks.

Pre-requisites

CSCI 4020 or an equivalent undergraduate algorithms course is a pre-requisite for this class, and will be strictly enforced. Students are assumed to be familiar with the basics of data structures and algorithms, discrete mathematics, and probability. Specifically, knowledge of the following will be assumed:

Books

There is no required book for this course. However, it is recommended that you purchase a copy of:

It is available at the campus store, and you should find it helpful as a supplement to the lectures. Other books which should be very useful for reference and for different perspectives are:

Homework, Exams, and Grading

Homeworks will be assigned approximately every 2 weeks. There will not be any programming assignments. Homeworks should be handed in at the end of lecture on the day they are due. Late homeworks will not be accepted, except in case of a genuine emergency.

You are allowed (and encouraged) to discuss homework problems with other members of the class, and to formulate ideas together. However, everyone must write up their assignments separately, and include the names of everyone you discussed the assignment with. You may not copy a solution from another. Failure to write the solution to a homework completely on your own will be considered a breach of academic integrity, and will be penalized severely.

You are required to prove your statements, unless otherwise specified. If a homework or exam question asks you to design an algorithm for a certain task, then the answer must consist of a description of the algorithm (an English description is fine), as well as an analysis of its running time and a proof of its correctness.

There will be a take-home final exam at the end of the semester. Unlike the homeworks, you must complete it entirely on your own. The final exam will be worth 30% of your grade, and the homework will be worth 70%.