Reading
Books and Lecture Notes
[Eri] J. Erickson. Algorithms. UIUC.
[Go] M.. Goemans. 18.438: Advanced Algorithms. MIT, 2008.
Linear Programming
- [AHK] S. Arora, E. Hazan, S. Kale, The Multiplicative Weights Update Method, Theory of Computing 8.1 (2012), 121-164.
- [BTM] S. Bradley, A. Hax, T. Magnanti Applied Mathematical Programming, 1977.
- [BV] S. Boyd, L. Vandenberghe, Convex Optimization (2004), chapter 5.
- [Cla] K. L. Clarkson. Las Vegas Algorithms for Linear and Integer Programming when the Dimension is Small. J. ACM 42(2): 488-499 (1995).
- [Dan] G. B. Dantzig, Linear programming, Operations Research 50 (2002), 42-47.
- [PS] C. Papdimitrious and K. Steiglitz, Combinatorial Optimization, Prentice Hall, 1982.
- [Sch] A. Schrijver, Theory of Linear and Integer Programing, Wiley Interscience, 1986.
- [ST] Daniel A. Spielman, Shang-Hua Teng, Smoothed Analysis: An Attempt to Explain the Behavior of Algorithms in Practice, CACM, 2009, Vol. 52 No. 10, 76-84.
- [Tod] M.J. Todd, The many facets of linear programming, Mathematical Programming 91: 417-436 (2002).
Network Optimization
- [CKM+] 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.
- [GT] Goldberg, Andrew V., and Robert E. Tarjan, Finding minimum-cost circulations by canceling negative cycles. Journal of the ACM (JACM) 36, no. 4 (1989): 873-886.
- [HK] 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).
- [Kar] Karp, R. M. (1978). A characterization of the minimum cycle mean in a digraph. Discrete mathematics, 23(3), 309-311.
- [Kuh] Harold W. Kuhn: The Hungarian Method for the Assignment Problem. 50 Years of Integer Programming 2010: 29-47.
- [ST] D.D. Sleator and R.E Tarjan, A Data Structure for Dynamic Trees, J. Comp. SYst. Sci., 26 (1983), 114-122.
- [Spi] D. Spielman, Spectral Graph Theory & Its Applications.
- [Tar] R.E. Tarjan, Data Structures and Network Algorithms, SIAM, 1983.
Approximation Algorithms
Randomized Algorithms
- [AI] A. Andoni, P. Indyk: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM 51(1): 117-122 (2008)I
- [BM] Broder, A., & Mitzenmacher, M. (2004). Network applications of bloom filters: A survey. Internet mathematics, 1(4), 485-509.
- [HP] S. Har-Peled, Geometric Approximation Algorithms , AMS, 2011
- [Mu] S. Muthukrishnan, Data Streams: Algorithms and Applications, Foundations and Trends in Computer Science, Now Publishers Inc, 2005.
Similarity Search
- [Ai] A. Andoni, P. Indyk: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM 51(1): 117-122 (2008).
- [BHK] Blum, A., Hopcroft, J., & Kannan, R. (2016). Foundations of data science. Vorabversion eines Lehrbuchs.
- [CGHJ] Graham Cormode, Minos N. Garofalakis, Peter J. Haas, Chris Jermaine:
Synopses for Massive Data: Samples, Histograms, Wavelets, Sketches. Foundations and Trends in Databases 4(1-3): 1-294 (2012)
- [CM] Graham Cormode, S. Muthukrishnan:
An improved data stream summary: the count-min sketch and its applications. J. Algorithms 55(1): 58-75 (2005)
- [CY] Graham Cormode, Ke Yi: Small Summaries for Big Data. Cambridge University Press, 2020.
- [dBCKO] M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars, Computational Geometry: Algorithms and Applications. Springer-Verlag, 3rd ed., 2008.
- [GIW] 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.
Algebraic/Numerical Algorithms
- [BP] Belkin, Mikhail, and Partha Niyogi. "Laplacian eigenmaps for dimensionality reduction and data representation." Neural computation 15, no. 6 (2003): 1373-1396.
- [BSS+] Batson, J., Spielman, D. A., Srivastava, N., & Teng, S. H. Spectral sparsification of graphs: theory and algorithms. Communications of the ACM, 56(8), 87-94, 2013.
- [Lux] Von Luxburg, U. A tutorial on spectral clustering. Statistics and computing, 17(4), 395-416, 2007.
- [Moh] Mohar, B. The Laplacian spectrum of graphs. Graph theory, combinatorics, and applications, 2(871-898), 12, (1991).
- [RV] Roughgarden, T., & Valiant, G. (2016). CS168: The Modern Algorithmic Toolbox Lectures# 11 and# 12: Spectral Graph Theory.
- [Sch] Schwartz, Jacob T. Probabilistic algorithms for verification of polynomial identities. International Symposium on Symbolic and Algebraic Manipulation, pp. 200-215. Springer, Berlin, Heidelberg, 1979.
home | page top