Course projects
There will be an individual course project which contributes 55% to the course grade.
The purpose of the course project is to facilitate one's research by acquiring a deeper understanding on a specific algorithmic topic/technique.
The basic requirement is to read three papers on a topic and write a report.
Students are encouraged to pick any algorithmic topic close to their research interests.
Below are some potential projects and references.
Other possible topics: network coding, algorithmic game theory, mechanism design, belief propagation, clustering algorithms, distributed algorithms, etc...
- The rubber band method - How to use rubber bands to design algorithms?
- Internet algorithms - How to design algorithms for massive networks such as the World Wide Web?
- J. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM 46, 1999.
- N. Bansal, A. Blum, and S. Chawla, Correlation Clustering, Machine Learning 56, 89-113, 2004.
- J. Kleinberg and E. Tardos. Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields, Journal of the ACM, 49, 616-639, 2002.
- N. Ailon, M. Charikar, and A. Newman, Aggregating Inconsistent Information: Ranking and Clustering, Proceedings of the 37th ACM Symposium on Theory of Computing (STOC), 2005.
- Combinatorial auctions - Designing efficient algorithms for combinatorial auctions.
- P. Cramton, Y. Shoham, and R. Steinberg, Combinatorial Auctions, The MIT Press, 2006.
- S. Dobzinski, N. Nisan, and M. Schapira, Approximation Algorithms for Combinatorial Auctions with Complement-free Bidders, STOC 2005.
- U. Feige, On maximizing welfare when utility functions are subadditive, STOC 2006.
- Selfish routing - How selfish, noncooperative behaviours affect the network performance?
- Probabilstic methods - How to use probabilistic analysis to show the existence of combinatorial objects?
- Semidefinite programming in combinatorial optimization - Find out how semidefinite programming gives the best known approximation algorithms for several well-studied problems.
- L. Lovász, Semidefinite Programming and Combinatorial Optimization, Documenta Mathematica, Extra Volume ICM 1998, Vol III, 657--666, 1998.
- M.X. Goemans and D.P. Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming, J. ACM, 42, 1115--1145, 1995.
- Primal dual algorithms - Study this general and powerful algorithmic paradigm in combinatorial optimization and approximation algorithms.
- Randomized rounding - Using probabilistic analysis in the design of approximation algorithms.
- A. Srinivasan, Approximation algorithms via randomized rounding - a survey, Lectures on Approximation and Randomized Algorithms (M. Karonski and H. J. Promel, editors), Series in Advanced Topics in Mathematics, Polish Scientific Publishers PWN, Warszawa, pages 9-71, 1999.
- N. Young, Randomized Rounding without Solving the Linear Program, SODA 1995.
- P. Raghavan, C.D. Tompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, 7, 365-374, 1987.
- Rapidly mixing Markov chains - A general way to sample complicated combinatorial objects.
- L. Lovász and P. Winkler, Mixing Times, Microsurveys in Discrete Probability (ed. D. Aldous and J. Propp), DIMACS Series in Discrete Math. and theor. Comp. Sci., AMS 1998, 85--133.
- M. Jerrum, Counting, Sampling and Integrating: Algorithms and Complexity, Birkhauser, 2003.
- M. Jerrum, A. Sinclair, and E. Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries, Journal of the ACM, 51(4):671-697, 2004.
- A. Frieze, E. Vigoda, A survey on the use of Markov chains to randomly sample colorings, manuscript, 2006.
- The iterative rounding method - See how this technique provides a unifying framework for many network design problems.
- Topological methods in combinatorics - Take a closer look at some surprising applications of topological methods.
- J. Matousek, Using the Borsuk-Ulam theorem, Springer, 2003.
- L. Lovász, Topological methods in Combinatorics, lecture notes 1996.
- F. Su, Rental harmony - Sperner's lemma in fair division, Amer. Math. Monthly, 106(1999), pp. 930-942. (See also Francis Su's Fair Division Page.)
- G. Tardos, Trasversals of d-intervals - comparing three approaches, in Proceedings of the Second European Congress of Mathematics, Progress in Mathematics, Vol. 169, Birkhäuser, 1998, 234-243.
- Combinatorial nullstellensatz - Using mathematical theorems on polynomial equations to show the existence of certain combinatorial objects.