CS 666, Spring 2009
Project Guidelines
Due date: before August 14, Friday 5pm
Basically: pick a problem and a paper, read the paper,
and write a report about it (at most 10 pages).
You may choose a paper on your own (but see tips and suggestions
below). The paper should be about algorithms, of course, and
preferrably related to topics covered in class. In accordance with
the "spirit" of this course, the emphasis of the paper should be on
well-defined problems and algorithms with provable performance
guarantees (worst-case time, expected time, approximation factor,
competitive ratio, etc.). Implementations and experimental studies
are not required and are not the objective.
The Report:
The first part should be devoted to a clear statement of the problem
and a short survey of known results. For this, you may have to read
up on previous papers and do a literature search for the latest
results.
The second part should be an description, in your own words, of
the algorithm and/or analysis from your particular paper. You might
find that papers don't necessarily give the clearest explanation. So,
don't just paraphrase the paper's description. Rather, the objective
is to make the paper easier to understand, for example, by finding a
different way to look at the algorithm, using simpler notation,
highlighting ideas as you see them to be, adding examples and
intuition, etc. Be creative! With only 10 pages, don't try to
explain all the details in the paper if they are too complicated and
technical---an overview is more important. (If the paper contains
several algorithms, focus perhaps on just one.) But do point out
connections with ideas from previous papers as well as techniques we
have seen from class.
The final part should be your critique of the new ideas and results
from the paper, e.g., how they compare with previous (and subsequent)
results and known lower bounds, how practical they are, etc. Also state
open problems,
including any of your own, for future work in the area. (And if
through this process you are able to obtain improvements and solve an
open problem, I'd love to hear about it!)
Tips:
Ideally, each student should choose a different problem, so let
me know what you have decided on (e.g., by e-mail or during office hrs).
You do not have to choose the latest paper with the best result on a
problem; find one which is "relatively" recent (i.e., not already
described in existing books or surveys) and which you think you can
understand reasonably well.
To get a feel for recent research in algorithms and complexity, browse
through
conference proceedings such as FOCS
(IEEE
Sympos. on Foundations of
Computer Science, QA401.S95x), STOC
(ACM
Sympos. on Theory of Computing, QA267.A2), and SODA
(ACM-SIAM
Sympos. on Discrete Algorithms, QA76.6.A278). Final versions of papers
usually appear in journals.
The DBLP
web site provides links to publishers' electronic copies of many
papers. The CiteSeer site provides links to the
authors' own electronic copies of recent papers. The latter site also
tracks citations, which is handy for finding related papers.
Also try Google Scholar.
Examples:
Below is just a "random" list of suggested problems/papers. You are
encouraged to look for other problems on your own.
- Finding cycles of length 4, 5, etc.:
e.g., Yuster and Zwick
(2004)
- Dynamic connectivity:
the first general polylog result (amortized and randomized!)
was achieved by a simple beautiful method of
Henzinger
and King (1999)
- Alternatives to Fibonacci heaps:
Recently (2009),
Haeupler, Sen, and Tarjan showed how decrease-key can be
done in constant amortized time without "cascading cuts", by instead changing
the "ranks" of nodes...
- Variations on union-find:
e.g.,
Kaplan, Shafrir, and Tarjan. Also,
another
paper studied a problem that combines union-find
and heaps.
- Dynamic all-pairs shortest path: several recent
papers, e.g.,
Demetrescu and Italiano (2003), which also uses amortized analysis
- Randomized algorithms for geometric pattern matching:
Cardoze and Schulman (1998) gave randomized algorithms for
pattern matching, not for strings, but for one- and higher-dimensional
point sets.
- Another randomized exponential SAT algorithm:
Paturi, Pudlak, and Zane (1997) gave a 3-SAT algorithm
that came before Schoening's and was also quite simple.
Or consider deterministic 3-SAT algorithms, the latest of which
is by
Scheder (2008).
- More news on SAT: it is known that in every k-CNF formula,
there always exists a satisfying assignment if each clause has common variables with
at most 2^{k-2} other clauses.
Moser's recent award-winning paper (2009) describes a
simple randomized polynomial-time
algorithm (also based on local search)
that almost matches this existence result.
- Faster exponential algorithms for graph coloring:
two recent papers by
Bjorklund
and Husfeldt and
Koivisto
(2006), describing some surprisingly simple new algorithms.
- Faster exponential algorithms for your other favorite NP-complete
problem (e.g., independent set, TSP, ...)
- Approximation algorithms for maximum metric TSP:
e.g., Hassin
and Rubinstein (2002) gave a short, randomized approximation algorithm
for a "max" variant of the metric TSP problem.
- Approximation algorithms for maximum independent set:
Berman and
Furer described a simple local improvement algorithm with
approximation factor about D/5 (better than the naive greedy with
factor D+1) where D is the maximum degree.
- Approximation algorithms for set cover:
Levin gave the latest approximation result on the k-set-cover problem
using a
combination of greedy and local search approaches.
- Approximation algorithms for your other favorite NP-complete
problem: see the
compendium of NP-hard optimization problems for inspiration.
- An on-line knapsack problem:
Iwama and Taketomi investigated the competitive
ratio of a variant of the on-line bin packing problem
(the 1-bin case does not appear too complicated).
- An on-line coloring problem:
e.g.,
Epstein et al.
or
Azar et al. studied coloring of intervals
"with bandwidth" in an on-line setting
- Your other favorite on-line problem (secretary problems,
robot navigation, facility location or clustering, etc.).