Approximation Algorithms  COMP 670J
Fall Semester 2001  Class Project Info
As previously discussed, this class will require
completing one mediumsize 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 firstcome
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.
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:
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:

A list of all of the files on your disk, a short description
of what they do and how to use them.

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.

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.

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.
Projects:
I/O Specifications for all of the projects can be found
here.

MaxSat: (1/2 person) Implement
the Random (1/2biased 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 2approximation 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 MinimumSpanningTree and MinimumWeightedMatching
code that are required as subroutines.

Minimum Multicut: (1 person)
Implement the PrimalDual 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.

SetCover: (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 3approximation 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 4approximation
algorithm and the randomized 3approximation 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.
114, 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 129 of the book Online Computation and Competitive Analysis
by Allan Borodin and Ran ElYaniv (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.
213219. 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.