Reading

Lecture Notes

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

[Pl] S. Plotkin, CS261 - Optimization Paradigms, Stanford University, 2010.

Linear Programming

G. B. Dantzig, Linear programming, Operations Research 50 (2002), 42-47.
J. Matousek and B. Gaerther, Understanding and Using Linear Programming, Prentice Hall, 2006.
C. Papdimitrious and K. Steiglitz, Combinatorial Optimization, Prentice Hall, 1982.
A. Schrijver, Theory of Linear and Integer Programing, Wiley Interscience, 1986.
[Go] M. Goemans, Linear Programming Notes, More recent notes
M.X. Goemans and D.P. Williamson, The primal-sual method for approximation algorithms and its application to network design problems, in Approximation Algorithms, D. Hochbaum, Ed., 1997. pdf
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

D. D. Sleator and Tarjan, A Data Structure for Dynamic Trees, J. Comp. SYst. Sci., 26 (1983), 114-122.
D. Spielman, Spectral Graph Theory & Its Applications
I. Abraham, D. Delling, A. V. Goldberg, R. Fonseca, and F. Werneck: Hierarchical Hub Labelings for Shortest Paths. Proc. 20th Annual European Symposium 2012: 24-35
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
R. E. Tarjan, Data Structures and Network Algorithms, SIAM, 1983
Pravin M. Vaidya: Geometry Helps in Matching. SIAM J. Comput. 18(6): 1201-1225 (1989)
H. W. Kuhn, The Hungarian method for the assignment problem, Naval Res. Logist Quart., 2 (1955), pp. 83-97.
Zvi Galil, Silvio Micali, Harold 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)

PLS completeness

David S. Johnson, Christos H. Papadimtriou, and Mihalis Yannakakis. 1988. How easy is local search?. J. Comput. Syst. Sci. 37, 1 (August 1988), 79-100.

Approximation Algorithms

Geometry

[DO] S. Devadoss and J. O'Rourke, Discrete and Computational Geometry, Princeton University Press, 2011
[HP] Sariel Har-Peled. Geometric Approximation Algorithms
Aristides Gionis, Piotr Indyk, Rajeev Motwani: Similarity Search in High Dimensions via Hashing. VLDB 1999: 518-529
Alexandr Andoni, Piotr Indyk: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM 51(1): 117-122 (2008)
[Mat] J. Matousek, Lectures on Discrete Geometry, Springer, 2002.