15-859(E): Advanced Algorithms, Fall 2009

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(m sqrt{n})$ 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.)
  • Clarification of the lecture
  
  
• 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: