• Administration
• Synopsis
• Grading
• Lectures
• Reading
• Assignments

Reading

Lecture Notes

[Ed] H. Edelsbrunner. CPS230 Lecture Notes. Duke University, 2008.

[Er] J. Erickson. CPS473G: Algorithms Lecture Notes. UIUC.

Linear Programming

• G. B. Dantzig, Linear programming, Operations Research 50 (2002), 42-47.
• [Go] M. Goemans, Linear Programming Notes, More recent notes.
• M.X. Goemans and D.P. Williamson, The primal-dual method for approximation algorithms and its application to network design problems, in Approximation Algorithms, D. Hochbaum, Ed., 1997. pdf
• C. Papdimitrious and K. Steiglitz, Combinatorial Optimization, Prentice Hall, 1982.
• A. Schrijver, Theory of Linear and Integer Programing, Wiley Interscience, 1986.
• T. Terlaky, An easy way to teach interior-point methods, European J. Operations Research, 130 (2001), 1-19.
• M.J. Todd, The many facets of linear programming, Mathematical Programming 91: 417-436 (2002).

Network Optimization

• P. Christiano, J.A. Kelner, A. Madry, D.A. Spielman, S.-H. Teng: Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs. Proc. 43rd ACM Symposium on Theory of Computing, 2011, 273-282.
• Z. Galil, S. Micali, H.N. Gabow: An O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs. SIAM J. Comput. 15(1): 120-130 (1986).
• D.D. Sleator and R.E Tarjan, A Data Structure for Dynamic Trees, J. Comp. SYst. Sci., 26 (1983), 114-122.
• D. Spielman, Spectral Graph Theory & Its Applications.
• R.E. Tarjan, Data Structures and Network Algorithms, SIAM, 1983.
• John E. Hopcroft, Richard M. Karp: An n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs. SIAM J. Comput. 2(4): 225-231 (1973).
• Harold W. Kuhn: The Hungarian Method for the Assignment Problem. 50 Years of Integer Programming 2010: 29-47.

Intractability

• M. Garey and D.S. Johnson, Computers and Intractability, Freeman, 1979.
• D.S. Johnson, C.H. Papadimtriou, and M. Yannakakis. 1988. How easy is local search?. J. Comput. Syst. Sci. 37, 1 (August 1988), 79-100.

Approximation Algorithms

• M.X. Goemans, D.P. Williamson: Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM 42(6): 1115-1145 (1995).

Geometry

• A. Andoni, P. Indyk: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM 51(1): 117-122 (2008).
• [dBCKO] M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars, Computational Geometry: Algorithms and Applications. Springer-Verlag, 3rd ed., 2008.
• A. Gionis, P. Indyk, R. Motwani: Similarity Search in High Dimensions via Hashing. VLDB 1999: 518-529.
• [Mat] J. Matousek, Lectures on Discrete Geometry, Springer, 2002.

Large Scale Computation

• [Mu] S. Muthukrishnan, Data Streams: Algorithms and Applications, Foundations and Trends in Computer Science, Now Publishers Inc, 2005.
• [Ru] R. Rubinfeld, Surveys and materials: Sublinear Time Algorithms.

page top