Course Information:
Lectures: MW 3-4:30, Room CCB 17Recommended Text: Randomized Algorithms by Motwani and Raghavan
Office hours: CCB 239, Monday, Wednesday 4:30-5:30, Thursday 2
TA: Deeparnab -- Office hours: CCB common area, Tu 1-2, deepc@cc
Exam: Take home final.
Lecture notes (these are notes from courses elsewhere, intended just as a reference for this course):
- Approximation algorithms:
- Aug 24: Vertex cover, set cover, randomized rounding (CMU)
- Aug 29, 31: VC, set cover, TSP (Berkeley)
- Sep 7: knapsack (Berkeley)
- Randomized algorithms:
- Sep 12: k-wise independence, linearity of expectation, quicksort
- Sep 12: Karger's min-cut algorithm
- Sep 14: Markov's inequality, Chebyshev's inequality, Chernoff bounds, complexity classes (See also this and this )
- Sep 19: Universal hash functions.
- Sep 21: The power of two: balls and bins
- On-line algorithms:
- Sep 26: Intro to on-line algs; paging
- Sep 28: Randomized paging
- Oct 3: The k-server problem
- Oct 5: Randomized ski-rental
- Computational Geometry
- Oct 10: Finding convex hulls
- Oct 12: Voronoi regions and Delaunay triangulations
-
***Papers (or almost polished drafts awaiting some feedback) are due
October 19!!***!
- OCT 24: Multicommodity flow
Luke Snyder and Sang-Ho Shim
Lecture notes
- Tom Leighton and Satish Rao, Multicommodity max-flow min-cut thoerems and their use in designing approximation algorithms. JACM 1999.
- C. Chekuri, S. Khanna, and B. Shephard, The all or nothing multicommodity flow problem. STOC 2004.
- OCT 26: Randomized rounding and semi-definite programming
Yan Shu and Fei Qian
Lecture Notes
- M. Goemans and D. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semi-definite programming. JACM, 1995.
- D. Karger, R. Motwani and M. Sudan, Approximate graph coloring by semidefinite programming. JACM, 1998.
- OCT 31: Oblivious routing schemes
Amin Ali and Gurashish Brar
Lecture Notes
- H. Racke, Minimizing congestion in general networks FOCS 2002.
- M. Bienkowski, M. Korzeniowski and H. Racke, A practical algorithm for constructing oblivous routing schemes. SPAA 2003.
- NOV 2: (See above lecture notes on Eigenvectors and Expanders)
- NOV 7: Power-law degree distributions
Dan Steffy and Burak Karacik
Lecture Notes
- A. Fabrikant, E. Koutsoupias, C. Papadimitiou, Heuristically optimized trade-offs: a new paradigm for power laws in the internet. Proc. 29th International Colloquium on Automata, Languages and Programming, 2002.
- D. Achlioptas, A. Clauset, D. Kempe, C. Moore, On the bias of traceroute sampling: or, power-law degree distributions in regular graphs. STOC 2005.
- NOV 9: Preferential attachment and scale-free graphs
Keshav Attrey and Muhammad Mukarram Bin Tariq
Lecture Notes
- R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, E. Upfal, Stochastic models for the web graph. FOCS 2000.
- M. Mihail, C. Papadimitriou, A. Saberi, On certain connectivity properties of the internet topology. FOCS 2003.
- NOV 14: Spectral analysis of data
Adam O'Neill and Arya Irani
Lecture Notes
- J. Kleinberg, Authoritative sources in a hyperlinked environment. SODA.
- Y. Azar, A. Fiat, A. Karlin, F. McSherry, J. Saia, Spectral analysis of data. STOC 2001.
- NOV 16: Expanders and ST-connectivity
Adam Marcus and Jaswanth Sreeram
Lecture Notes
- O. Reingold, S. Vadhan and A. Wigderson, Entropy waves, the zig-zag product, and new constructions of constant-degree expanders. FOCS 2000.
- O. Reingold, Undirected ST-connectivity in log-space. STOC 2005.
- NOV 21: Max independent sets of axis aligned rectangles
Teena Carroll and Ye Yan
Lecture Notes
- N. Mustafa, Approximation algorithms for independent sets of rectangles when the independent set is large.
- L. Lewin-Eytan, S. Naor and A. Orda, Routing and admission control in networks with advance reservations. APPROX 2002.
**Take Home Final handed out.**
- NOV 28: Alternatives to competitive analysis
Giorgos Amanatidis
Lecture Notes
- E. Koutsoupias and C. Papadimitriou, Beyond competitive analysis. SIAM J. Comp., 2000.
- J. Boyar, K. Larsen and M. Nielsen, The accomodating function: a generalization of the competitive ratio. SIAM J. Comp., 2000.
- NOV 30: Generalizations of ski-rental
Joe Chung and Hisham Harik
- O. Goldreich and L. Trevisan, Three theorems regarding testing graph properties. Random Structures and Algorithms, 2003.
- Dec 5: Property testing
Mitch Keller and Farhan Khan
- Dec 7: PTAS for Euclidean TSP
Jeff Yunes and Selin Calinskan
- S. Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. JACM, 1998.
- A. Dumitrescu and J. Mitchell, Approximation algorithms for TSP with neighborhoods in the plane. J. Algs., 2003.
THE LATEX TEMPLATE (for writeups on presentations)
(The first two presentations must get their drafts to me by October 12!)
Remember that these topics and suggested papers are meant to be a guide. Some of you will find that one of these papers suffices for a good lecture, October 19!!***!
(The first two presentations must get their drafts to me by October 12!)
Remember that these topics and suggested papers are meant to be a guide. Some of you will find that one of these papers suffices for a good lecture, October 19!!***!
(The first two presentations must get their drafts to me by October 12!)
Remember that these topics and suggested papers are meant to be a guide. Some of you will find that one of these papers suffices for a good lecture, while others will find that they need to do a literature search and include more papers for a comprehensive lecture. You are not expected to cover everything in these papers, but to extract an interesting 1.5 hour lecture that will be understandable, interesting, and informative for the class.
TENTATIVE SCHEDULE:
-
**Take Home Final due -- DEC 5 in class!!**