15-859(E): Advanced Algorithms, Fall 2009 (original) (raw)
Lecturers: Anupam Gupta and Danny Sleator
Time: MW 3:00-4:20, GHC 4303
Course Blog: http://cmu-advancedalgorithms.blogspot.com/
Lectures
Lecture 1: MSTs: intro, Prim, Kruskal, Boruvka, O(m log log n) time using Fibonacci heaps, Fredman-Tarjan and O(m log* n) time
- Bob Tarjan's lecture notes on MST algorithms
- Eisner's survey on MST algorithms
- Graham and Hell's survey (CMU only, 20M file)
Lecture 2: Heaps: Fibonacci heaps. (Sleator's Notes)
Lecture 3 & 4: Analysis of disjoint set algorithms
- Rough scribe notes from lecture #3.
- Top-Down Analysis of Path Compression By Raimund Seidel and Micha Sharir
- Seidel's talk at Tarjan's festschrift
Lecture 5: A linear-time Randomized MST algorithm. Finding min-cost arborescences.
- The Karger Klein Tarjan paper: A randomized linear-time algorithm to find minimum spanning trees, JACM.
- Timothy Chan, Backwards Analysis of the Karger-Klein-Tarjan Algorithm for Minimum Spanning Trees. Inf. Process. Lett. 67(6): 303-304 (1998)
Papers related to linear-time algorithms for MST verification and finding F-light edges: - R.E.Tarjan, Applications of path compression on balanced trees. JACM.
- Janos Komlos, Linear verification for spanning trees, Combinatorica.
- B. Dixon, M. Rauch, R. Tarjan, Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time, SICOMP.
- Valerie King, A simpler minimum spanning tree verification algorithm, Algorithmica.
And papers on finding optimal branchings. - R. Tarjan, Finding optimal branchings, Networks: an O(m log n) time algorithm. (and errata by Carmerini et al.)
- Gabow, Galil, Spencer and Tarjan. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica.
- Mendelson, Tarjan, Thorup, Zwick. Melding priority queues, ACM TAlg (SODA 04, STACS 04).
Lecture 6 (9/28): Finding Shortest Paths I. Ford, Dijkstra (and some implementations), Bellman-Ford(-Moore), (valid) potentials and negative cycles, Floyd-Warshall, Seidel.
- The basics: Jeff Erikson's lecture notes on SSSP, APSP.
- Chapter on shortest-paths from Korte and Vygen.
- Workshop on shortest-path algorithms from 2005, including a survey by Andrew Goldberg on SSSP.
Papers related to today's material. - R. Seidel. On the all-pairs-shortest-path problem, STOC 1992.
Problems 4&5 from homework 2 are drawn from this paper, so please do not read it if you want to solve those problems. - Alon, Galil, Margalit, Naor. Witnesses for Boolean Matrix Multiplication and for Shortest Paths, FOCS 92.
- A. Shoshan, U. Zwick. All pairs shortest paths in undirected graphs with integer weights, FOCS 99.
Lecture 7 (9/30): Shortest Paths II. Finding potentials faster than Bellman-Ford.
- A. Goldberg, Scaling Algorithms for the Shortest Paths Problem, SICOMP.
- Uri Zwick's notes on Goldberg's algorithm.
Lecture 8 (10/5): van Emde Boas data structure. Perfect hashing.
- Peter van Emde Boas, R. Kaas, and E. Zijlstra: Design and Implementation of an Efficient Priority Queue, Mathematical Systems Theory 1977.
- Notes from Erik Demaine's course, and from Gudmund Frandsen
Lower bounds. - Paul Beame and Faith Fich. Optimal bounds for the predecessor problem and related problems. JCSS.
- Mihai Patrascu and Mikkel Thorup. Time-Space Trade-Offs for Predecessor Search, STOC 06.
Perfect Hashing. - Notes from Erik Demaine's class.
- M. Fredman, J. Komlos and E. Szemeredi, Storing a Sparse Table with O(1) Worst Case Access Time, JACM.
- M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert and R.E. Tarjan, Dynamic Perfect Hashing: Upper and Lower Bounds, FOCS 88.
Lecture 9 (10/7): Fully-dynamic graph connectivity in O(log^2 n) update time.
- J. Holm, K. de Lichtenberg, M. Thorup.Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, JACM.
- Notes from Erik Demaine's class.
Lecture 10 (10/12): Network Flows
- Max-flow notes from Dexter Kozen's book. (CMU/Pitt only.)
- Notes on push-relabel from a survey by Andrew Goldberg, Eva Tardos and Bob Tarjan. (CMU/Pitt only.)
Including details on efficiently implementing the algorithm.
Lecture 11 (10/14): Splay Trees. Dynamic Trees (part I).
- Lectures on Splay Trees (1, 2) from the Advanced Data Structures course.
- These notes (3) from Graduate Algorithms (1999) reflect the analysis (using real logs) presented in class.
- D. D. Sleator and R. E. Tarjan.Self-Adjusting Binary Search Trees, JACM 85.
- D. D. Sleator and R. E. Tarjan, A Data Structure for Dynamic Trees, JCSS 83.
Lecture 12 (10/19): Matchings, bipartite and non-bipartite, unweighted and weighted.
- Notes from Michel Goemans' combinatorial optimization course on bipartite and non-bipartite matchings.
- Lex Schrijver's proof of the Tutte-Berge formula.
- Schrijver's notes on combinatorial optimization.
Chapters 3 and 5 cover bip. and general matchings, and Chapter 4 contains the Even-Tarjan and O(msqrtn)O(m sqrt{n})O(msqrtn) analyses. - Matchings using the Tutte matrix (notes from our Randomized Algos course); the classic Mulmuley-Vazirani-Vazirani paper.
The proof of the theorem for the bipartite case is easy, the non-bipartite case is proved here. - The Lovasz-Plummer book appears to be available in a new printing by the AMS!
Lecture 13 (10/21): Dynamic trees (contd.)
Lecture 14 (10/26): Large Deviation (aka Chernoff-type) Bounds, Martingales and Azuma-Hoeffding.
- Some beautiful notes by Jiri Matousek and Jan Vondrak.
- Notes on Chernoff bounds from our randomized algorithms course.
- Need some advanced concentration inequalities? Look at these notes by Gabor Lugosi.
- Or check out the new Dubhashi-Panconesi book on concentration of measure.
- Or these fine books by Alon & Spencer, Motwani & Raghavan, Mitzenmacher & Upfal, Steele, and Janson, Luczak, Rucinski.
Lecture 15 (10/28): Polyhedra, Linear Programs, Duality.
- Lecture notes by Michel Goemans on the basics.
Lecture 16 (11/02): Solving LPs via the Ellipsoid method.
- The Kalai and Kleitman bound on the diameter of (1-skeleton) of polyhedra.
- Lecture notes by Michel Goemans on the Ellipsoid Method.
- The chapter on the Ellipsoid method in the Korte-Vygen book is very readable, and gives a lot more detail than we did in class.
- The classic GLS (Groetschel, Lovasz, Schrijver) book is where you get all the details.
- A reduction from separation to membership for polyhedra. The general reduction is more involved.
Lecture 17 (11/04): The Matching Polytope, Integrality of the bipartite matching polytope.
- Michel Goemans' lecture notes recommended for Lec 15 contain some of the ideas from this lecture too.
Lecture 18 (11/09): Max-flow min-cut proof, Seidel's linear-time LP algorithm.
- Seidel's original paper.
- Suresh Venkatasubramanian's notes give the details on solving the recurrence that I glossed over in lecture.
Some more references, in case you're interested. - Sariel Har-Peled's notes on low-dimensional-LPs.
- Dyer, Megiddo and Welzl's survey on geometric LPs gives refs and context.
- Seidel's notes on backwards analysis, including notes on his _O(d! n)_-time LP algorithm.
Backwards analysis is a cool technique, we might try to cover it in one of the lectures.
Lecture 19 (11/11): More low-dimensional LPs, and reweighting techniques.
- K. Clarkson, Las Vegas algorithms for linear and integer programming when the dimension is small, JACM.
- J. Matousek, E. Welzl and M. Sharir, A subexponential bound for linear programming, Algorithmica 16 (1996) 498-516.
- A survey by Avrim about Online Learning, which presents the weighted majority analysis, and talks about many applications.
Lecture 20 (11/16): Online algorithms: ski-rental, list update, paging and k-server problems.
- Danny's notes on ski-rental and list-update.
- Danny's notes and Avrim's notes on paging and migration problems
Lecture 21 (11/18): A (very) brief introduction to Approximation algorithms (Part I).
- You can check out the first couple of lectures from the Spring 08 advanced approximation algorithms course for the set cover analysis.
- P. Slavic, A Tight Analysis of the Greedy Algorithm for Set Cover, J.Alg.
- U. Feige, A Threshold of ln n for Approximating Set Cover. JACM.
Lecture 22 (11/23): A (very) brief introduction to Approximation algorithms (Part II)
- M. Goemans and D. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, JACM.
- Alekhnovich, Arora and Tourlakis's paper on Lovasz-Schrijver lifts: Appendix B.1 contains a proof that max-cut.
- Laci Lovasz's survey on semidefinite programming. Talks about solving SDPs, duality, and other fun stuff.
And some of the recent developments on Max-Cut. - Feige and Schechtman showed tight integrality gaps for the SDP.
- The Khot Kindler Mossel O'Donnell paper showing that the 0.878 factor is best possible for Max-Cut, assuming the Unique Games Conjecture.
- O'Donnell and Wu: Optimal SDP Rounding Algorithms for Max-Cut, STOC 08.
- Raghavendra and Steurer: SDP Rounding algorithms for any k-CSP, FOCS 09. (and the talk.)
Lecture 23 (11/30): Planar point location using persistent search trees.
- Sarnak, Tarjan. Planar point location using persistent search trees, CACM.
- Driscoll, Sarnak, Sleator, Tarjan. Making Data Structures Persistent
Lecture 24 (12/2): Online algorithms revisited: randomized rent-or-buy two different ways.
- Karlin, Manasse, McGeoch, Owicki: Competitive randomized algorithms for non-uniform problems
- The paper of Karlin, Kenyon(-Mathieu), Randall: Dynamic TCP acknowledgement and other stories about e/(e-1), STOC 01.
- A talk on randomized ski-rental by Maurice Queyranne.
The technique of solving LPs online: - Buchbinder, Naor: The Design of Competitive Online Algorithms via a Primal-Dual Approach. NOW Publishers.
- Three lectures by Seffi Naor on the topic. (towards the end of the page)
And two recent papers about the randomized k-server problem based on online LPs. - Bansal, Buchbinder, Naor. Towards the Randomized k-server Conjecture: A primal-dual approach, SODA '10.
- Bansal, Buchbinder, Naor. Metrical Task Systems and k-server problem on HSTs, manuscript.
Homework:
Homework 1 (due Monday, September 28, beginning of class)
Homework 2 (due Monday, October 12, beginning of class)
Homework 3 (due Monday, November 23, beginning of class)
Maintained by Anupam Gupta and Danny Sleator