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:

Deadlines:

• November 23,  2001:  By this date you should send me email at golin@cs.ust.hk with your first and second choice for a project.  Your email should include your name, ID number,  email address and first and second choices for the project. If you want to work on a project not on the list please contact me before the deadline to discuss your proposal.

 
• December 3,  2001:     By this date you should  email me a short description of how you will generate the data upon which you will test the performance of your program.

• December 22,  2001:  Hand in your project by 11:00 AM.  (Details of where, to be provided later).

 

Notes:

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.

Projects:

• MaxSat: (1/2  person)    Implement the Random (1/2-biased coin) algorithm, Randomized Rounding and the Best of Two algorithms.  Compare the solutions to each other and to the solution to the relaxed LP.

 
• Travelling Salesman: (1/2  person)     Implement the  2-approximation and 3/2 -approximation algorithms described in class for the metric traveling salesman problems. Also implement a dumb algorithm calculating the exact solution. Compare the solutions given by the two approximation algorithms to each other and to the exact solution. You may assume that the input vertices will be points in the plane and that the weight of the edge connecting two points will be the physical distance between them. Note:  the major work in this project will involve implementing the Minimum-Spanning-Tree and Minimum-Weighted-Matching code that   are required as subroutines.

 
•  Minimum Multicut:  (1 person)     Implement the Primal-Dual Minimum Multicut algorithm for trees. When testing the algorithm compare the solution produced by the algorithm to the solution produced by solving relaxed primal Linear Program.

 
•  Set-Cover:  (1/2 person)    Implement the Greedy algorithm (lecture 2) and the Randomized Rounding algorithm.  Compare the solutions against themselves and against the solution to the relaxed linear program.   Also, for the Randomized Rounding algorithm,  implement a variation that outputs a  minimal cover.  That is,  generate the randomized rounding cover and then throw away sets (maintaining the property that what you have is a cover) stopping when no more sets can be thrown away.

 
• Minimum Makespan:  (2/3 persons)    Implement the PTAS described in class along with an exact algorithm.  Compare the solutions found by  the PTAS with different approximation ratios and with the exact solution

 
• Shortest Superstring:  (1/2 person)    Implement the 4 -approximation algorithm we learnt in class,  Also implement the 3-approximation algorithm described at the end of Vazirani,  chapter 7 (this uses a greedy set cover algorithm from section 2.3  as a subroutine).  Compare the solutions given by the two algorithms.

 
• FPTAS for Knapsack:  (1/2 person)    Implement the FPTAS for Knapsack described in Chapter 8 of Vazirani's book.  Also implement an exact algorithm for solving the problem. Compare the solution of the FPAS for various approximation ratios to each other and to the optimal solution.

 
• Uncapacitated Facility Location:  (2/3  persons)    Read Chapter 12 in Williamson's notes  (Fall 1998) and implement the deterministic  4-approximation algorithm and the randomized 3-approximation algorithm. Compare the solutions to each other. Also, when testing the algorithms compare the two solutions produced to the solution produced by solving the relaxed Linear Program.

 
• Sonet Rings: (1/2 person)     Read the paper ``The Ring Loading Problem'' by A. Schrijver. P. Seymour and P. Winkler, SIAM Journal on Discrete Math,11(1), pp. 1-14, February 1998. Implement the algorithm described in the paper.  The paper can be downloaded through the UST library online journals page

 
• The List Accessing Problem:  (2/3person)     Read pages 1-29 of the book Online Computation and Competitive Analysis by Allan Borodin and Ran El-Yaniv (available from the  library or the instructor).  Implement some of the online algorithms described there for the problem,  and compare their behaviors.  As part of this project you must state in advance which of the online algoritms you will be implementing.

 
• Approximation Algorithms for Clustering:  (2/3 persons)    If you attended the department seminar given by Professor David Mount a few weeks ago you saw some approximation algorithms for the clustering problem.  This project is to implement the algorithms and compare them.  For more details please contact Professor Mount directly at  dmount@cs.ust.hk.

•  FPTAS  for the Restricted Shortest path problem: (2/3 persons)   Read the paper  "A simple efficient approximation scheme for the restricted shortest path problem,"  by Dean Lorenz and Danny Raz,  Operations Research Letters, 28, pp. 213-219.  Implement the FPTAS  described.  Also implement an exact algorithm for solving the problem. Compare the solution of the FPTAS for various approximation ratios to each other and to the optimal solution. The paper can be downloaded through the UST library online journals page

 
• Anything else that might be interesting:  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.