CS G399: Topics in Theory: Approximation Algorithms
Spring 2004
Instructor: Rajmohan
Rajaraman
113 Cullinane
Hall
Work: 617-373-2075
College of Computer
Science
Email: rraj@ccs.neu.edu
Northeastern
University
Home: 617-232-8298
Boston, MA
02115
Fax: 617-373-5121
Class meeting times/location: W
6:00-9:00 PM
Office Hours: M 4:00-5:00 PM and W
2:00-3:00 PM
Course Description Textbook Prerequisites Grading
Problem Sets Class Participation Project
Tentative
Class Schedule (Will include all handouts)
NOTE: The first class for
the course will be held on Wednesday, Jan 14. Since the instructor
will be out of town during the first week of classes, there will be no
class on Jan 7.
Course Description
This course will focus on the design and analysis of approximation algorithms. The
study of approximation algorithms has developed from the seeming
intractability of a number of widely-applicable NP-hard
optimization problems. These optimization problems are unlikely to
admit efficient (polynomial-time computable) optimal solutions.
Consequently, a number of techniques have been designed to provide
approximate (near-optimal) solutions that can be obtained
efficiently. Of course, we would like to sacrifice as little
optimality as possible, while gaining as much as possible in
efficiency. Trading off optimality in favor of efficiency is the
paradigm of approximation algorithms.
Approximation algorithms have recently gained significant attention
with the development a number of new techniques this decade. These
techniques range from simple ones like greedy
algorithms, randomization,
and dynamic programming, to
more sophisticated techniques based on linear
programming and more recently, semidefinite
programming. Moreover, these techniques have been applied to a
variety of different problems in diverse areas including artificial
intelligence, databases, distributed systems, information retrieval, and
networking.
The goal of this course is to present and analyze the various
techniques in approximation algorithms in the context of different
applications. Topics covered will be selected from the following:
- Background: Brief review
of complexity theory, the classes P and NP, the notion of NP-hardness,
polynomial-time reductions.
- Framework for analyzing
approximation algorithms: approximation ratio, different notions
of approximations.
- Techniques:
- Elementary methods: greedy algorithms, basic randomization, and
dynamic programming.
- Techniques based on linear programming: Randomized rounding and
the primal-dual method.
- Other techniques based on mathematical programming (time
permitting): Lagrangian relaxations and semidefinite programming.
- Problems: Vertex cover,
set cover, feedback vertex set, shortest superstring, knapsack,
bin-packing, traveling salesperson problem (TSP), facility location
(e.g., k-center, k-median), clustering, max-cut, and others.
- Example application areas:
We will discuss scenarios in which the above problems arise.
Example application domains include computational biology,
databases, data mining, information retrieval, networking, and parallel
and distributed computing.
- Other topics:
- Online computation: The
class of problems in which the input is provided online (dynamically),
and decisions have to be made with incomplete information.
- Distributed algorithms:
Here computation is being done by multiple processors, each having
access to only a part of the input. Consequently, in many
scenarios, only approximate solutions can be obtained efficiently.
- Hardness of approximation:
Over the past decade, a set of remarkable results has shown that many of
the NP-complete problems are, in fact, even hard to approximate.
Time-permitting, we will give a brief introduction to the main
result and its applications.
The above is probably more than what we will be able to cover.
The list should give you a good flavor of what we would like to
cover, and how extensive the course can be, given more time!
Required Textbook
Vijat Vazirani, Approximation Algorithms, Springer-Verlag,
Berlin, 2001. Available from Amazon, Barnes & Noble,
and other book stores for $35-40.
We will also use additional material to illustrate the applications
of problems we will cover in the course.
Prerequisites
The only prerequisite for this course is a graduate course in
algorithms (COM 3390, COM 3392, CSG 713, or equivalent). The
student must be familiar with greedy algorithms, dynamic programming,
graph algorithms for minimum spanning trees, and shortest paths.
Familiarity with the theory of NP-completeness will be an asset,
although not required. A review of NP-completeness will be done in
the first class meeting. It is recommended that the student review the
material on NP-completeness given in Chapter 36 of Introdution to
Algorithms, Cormen, Leiserson, and Rivest, MIT Press, 1990.
If you are interested in taking the course and are not sure whether you
satisfy the prerequisites, please contact the instructor.
Grading
Since this is an advanced course, we will generally avoid
stress-inducing activities such as tests. The course grade will be based
on four problem sets (worth 30\%), class participation (10\%), and a
project (60\%).
Problem Sets
Students will not be required
to turn in written solutions to the problems. Instead, we will
have separate problem-solving sessions
for each problem set, 1-2 weeks following the day the problem set is
handed out. We will discuss solutions to the problems during these
sessions, which may be held separately from the regular class times.
The discussion for each problem will be led by designated
student(s). Every student is expected to attempt each problem and
participate actively in the problem-solving sessions. Following the
session, the designated student(s) must write up a solution for the
problem and submit it.
Class Participation
Since this is expected to be a small class, I am hoping that the
lectures are interactive, with discussions leading toward improved
understanding of technical material, and identification of research
directions. The grade for class participation will be determined by the
extent and impact of the student's participation in class discussions.
Project
Students will be required to do a course project which could be any one
of the following types:
- Research Proposal:
Students pursuing research (or interested in pursuing research) in
approximation algorithms or application areas in which approximation
algorithms arise are encouraged to work on a research proposal as a term
project. This will involve identifying a specific domain,
reviewing literature related to the domain, and then formulating at
least one well-defined problem in the area, that merits further
research. Furthermore, the student must propose at least one
viable direction for solving the proposed problem. Topics for
research proposals are best chosen from the student's current research
area, with significant feedback from the instructor.
- Research Project: The
student may work on an already-established research problem. S/he
would be expected to explore a potential solution technique to
significant depth. Suggested research problems will be provided by
the instructor. If the student is already working on a research
problem relevant to the course, then a well-defined piece of the problem
with specific goals can be chosen as a research project.
- Implementation project: In
an implementation project, the student will experimentally evaluate an
approximation technique or a set of approximation algorithms for an
optimization problem. Suggested topics for implementation projects
will be provided by the instructor.
- Survey project: The
student will perform a literature survey of a topic related to
approximation algorithms, and explore in depth at least one key result
in the area. Suggested topics for survey projects will be
provided by the instructor.
The project topics will be decided by the halfway point of the semester
(by the third week of February). The completion of the project
will have two deliverables:
- Document: A 5-page
document needs to be written for a research proposal, research project,
or a survey project. In the case of a research proposal, we will try to
follow NSF-style guidelines. In the case of a research project,
the document must detail the various technical ideas that the student
has explored. In the case of the survey project, the student must
motivate and classify the existing work in the area and provide a useful
bibliography. For the implementation, a shorter document giving
the implementation framework will suffice.
- Presentation: The last 2-3
weeks of the course are reserved for presentations. Each
presentation will range from 30-60 mins, depending on the size of the
class.
Sample project topics: Job
scheduling, multicommodity flows, data streams, approximability of
counting problems, metric space embeddings, hierarchical clustering,
time-approximation ratio tradeoffs for distributed algorithms, protein
folding, algorithm mechanism design, routing and admission control,
network design.