Approximation Algorithms --  COMP 670J

Fall Semester  2001 -- Class Project Info

As previously discussed, this class will require  completing one medium-size project. The project will be worth 50% of the final grade (not 40% as written  in the tentative grading scheme proposed at the beginning of the  semester).  Below you will find a list of possible projects.   Some  of the projects are recommended for one person while others are recommended for a one/two  or two/three person group.  (The number of persons recommended for the project is in parenthesis after the project title).

This project list is not meant to be exhaustive.  If you would like to do a project that is not on the list, e.g.,  implementing an algorithm we did not learn that is described in one of the class references or reading a  paper and implementing its contents,  please send   email with a description of what you  propose to do or come and see me; we can discuss what would be an appropriate workload.

Since the class is so large I expect many different individuals to be working on the same project.  When this happens your work should be your own. Please do not copy code or ideas from anyone else except your partner (if you are on a two/three  person project).

Also,  only seven individuals/groups will be permitted to work on any one project.  The projects will be allocated on a first-come first serve basis;  the first seven to request a project get to work on it.

Project FAQ:

The Project FAQ will be updated regularly with tips and answers to some of the
common questions being asked.  It is recommended that you check it every few days
or so to see what has been added.



When you complete your project you should hand in two things;the first will be a disk with your code on it. This includes both the algorithm code and  programs for generating test data.  The second will be a short printed report that contains the following information:
  1. A list of all of the files on your disk, a short description of what they do and how to use them.
  2. The address of a publically accessible directory where the source and executable versions of the files are available so that I can test out your programs on line.  The directory should contain a README file describing its contents.
  3. Comparison Data:  Each project requires you to compare your programs' solutions  to each other and sometimes to the optimum solution of a linear program.  Prior to December 3,  2001 you should decide on how you will generate the data on which you will test your algorithms and send me a short email describing this process.  I'll let you know if it's sufficient.
  4. Shortcomings:  Please describe the situations in which your program fails or becomes useless and explain why this happens.  For example,  the PTAS for  minimum makespan becomes slower and slower as the approximation factor approaches 1.  Please explain at what approximation factor  your algorithm will become useless and justify your explanation.
Finally,  many of the projects require solving linear programs. These linear programs are relatively simple and small, so any general purpose LP package will be able to solve them. There are a  variety of linear programming packages available off of the web.  The book,  Numerical Recipes in C, also has some good basic code for solving LPs.  For those of you doing projects requiring solving LPs, please feel free to share this code among yourselves;  solving the LPS is only a subroutine and is not intended to be the bottleneck of your project.


I/O Specifications for all of the projects can be found here.