Revision as of 20:56, 1 September 2009

Time: Wednesday 1:25-2:45pm (note the changed time)

Place: LCR (MEB 3147)

We will cover approximation algorithms this fall. more details later on...

Readings

Date	Paper(s)	Presenter
Sep 2	Basic methods: Vertex Cover and metric TSP	Suresh
Sep 9	Greedy algorithms: Set Cover, Makespan
Sep 16	Dynamic Programming: Knapsack, Bin Packing
Sep 23	Local Search I: MAX CUT, Facility Location (part I, II)
Sep 30	Local Search II: MAX CUT, Facility Location (part I, II) . Also see these simplified notes
Oct 7	LP rounding: Congestion
Oct 21	Primal Dual I: Steiner Trees, Facility Location
Oct 28	Primal Dual II: Steiner Tree, Facility Location
Nov 4	Approximations via Tree Embeddings
Nov 11	Sparsest Cut and Metric Embeddings I
Nov 18	Sparsest Cut and Metric Embeddings I
Nov 25	SDPs I: Basics and MAX CUT
Dec 2	SDPs II: Graph Coloring
Dec 9	MCMC

@@ Line 11: / Line 11: @@
 * [http://www.cs.utah.edu/~suresh Suresh Venkatasubramanian], Assistant Professor, School of Computing
 * [http://www.cs.utah.edu/~praman Parasaran Raman], PhD Student, School of Computing
-* [mailto:john.moeller@utah.edu John Moeller], PhD Student, School of Computing
+* [http://ontopo.wordpress.com/ John Moeller], PhD Student, School of Computing
 * [mailto:rajvarma@cs.utah.edu Raj Varma Kommaraju], MS Student, School of Computing
 * [mailto:teichert@cs.utah.edu Adam R. Teichert], MS Student, School of Computing