Reading

Linear Programming

[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.
[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.

Network Optimization

[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.
[Rg] Tim Roughgarden, Lecture Notes on the Hungarian Algorithm.
[Tar] R.E. Tarjan, Data Structures and Network Algorithms, SIAM, 1983.
[Zw] Uri Zwick, Lecture Notes on Maximum Bipartite Matching.

Approximation Algorithms

[AHK] S. Arora, E. Hazan, S. Kale, The Multiplicative Weights Update Method, Theory of Computing 8.1 (2012), 121-164.
[AV] D. Arthur, S. Vassilvitskii: k-means++: the advantages of careful seeding. SODA 2007: 1027-1035
[AMR] David Arthur, Bodo Manthey, Heiko Röglin: Smoothed Analysis of the k-Means Method. J. ACM 58(5): 19:1-19:31 (2011)
Ke Chen: On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications. SIAM J. Comput. 39(3): 923-947 (2009)
Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Sergei Vassilvitskii: Fair Clustering Through Fairlets. NIPS 2017: 5029-5037
Davin Choo, Christoph Grunau, Julian Portmann, Václav Rozhon: k-means++: Few more steps yield constant approximation. ICML 2020: 1909-1917
Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu: Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics. SIAM J. Comput. 48(2): 644-667 (2019)

Randomized Algorithms

[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

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).
[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.

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.