COM 3391: Advanced Algorithms: Topics in approximation algorithms

Fall 1999

Instructor:  Rajmohan Rajaraman

113 Cullinane Hall                                                                      Work: 617-373-2075
College of Computer Science                                                 Email: rraj@ccs.neu.edu
Northeastern University                                                           Home: 617-864-1596
Boston, MA 02115                                                                     Fax:    617-373-5121

Class meeting times/location:     W 5:15--8:15

Office Hours:    M 5:00--6:00 PM, W 2:00--3:00 PM

Course Description

Prerequisites

References

Grading

Project

Handouts (in postscript)

Course Information                            Exercise Set 1                        Lecture 1
Tentative Course Schedule                  Problem Set 1                      Lecture 2, part 1
Reading list                                         Sample Solution to PS1        Lecture 3, part 1
                                                          Problem Set 2                         Lecture 3, part 2
                                                           Sample Solution to PS2         Lecture 4
                                                           Problem Set 3                        Lecture 5
                                                                                                         Lecture 6
                                                                                                         Lecture 7
                                                                                                         Lecture 8
                                                                                                         Lecture 9

Course Description

This course will cover some basic topics in 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. Moreover, these techniques have been applied to a variety of different problems in diverse areas including databases, operating systems, 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:
 
  • Brief review of complexity theory: the classes P and NP, the notion of NP-hardness, polynomial-time reductions.

    •  
  • The framework for analyzing approximation algorithms: approximation ratio, different notions of approximations.

    •  
  • Techniques: greedy algorithms, dynamic programming, randomization, design and analysis techniques based on linear programming.

    •  
  • Network design problems such as the network survivability problem and minimum Steiner Tree problem (that arises in multicast routing).

    •  
  • Classic optimization problems such as the set cover problem and the traveling salesperson problem.

    •  
  • Facility location problems that arise in a wide range of applications in operations research and computer science; for example, the location of base stations in wireless networks, the location of fire stations in a city.

    •  
  • Online algorithms for load balancing, scheduling, and virtual circuit routing.

    •  
  • A brief introduction to hardness of approximations.

    •  

     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     

    Prerequisites

    The only prerequisite for this course is COM3390 (Analysis of Algorithms).  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.

    Textbook

    The material covered in the course will be taken from:
     
  • Introdution to Algorithms, Cormen, Leiserson, and Rivest, MIT Press, 1990.

    •  
  • Approximation Algorithms for NP-Hard Problems, edited by Dorit Hochbaum, PWS Publishing Company, 1997.

    •  
  • Recent research papers that will be handed out in class.

    •  
  • Notes on approximation algorithms by Michel Goemans, Rajeev Motwani, and Vijay Vazirani.

    • Grading

    The course grade will be based on two problem sets (each worth 15%), a midterm (30%),  and a project (40%).  Furthermore, each student is required to scribe one lecture.  We will put together the lecture notes as a manuscript at the end of the course.


     

    Project

    Students will be required to do a course project which could be any one of the following types:
     
  • An implementation project evaluating an approximation technique or different approximation algorithms for an optimization problem.

    •  
  • Presentation of a survey article or a research paper.

    •  
  • Work on a research problem.

    •