Reading

Lecture Notes

[Eri] J. Erickson. CPS473G: Algorithms. UIUC.

[Goe] M.. Goemans. 18.438: Advanced Algorithms. MIT, 2008.

Linear Programming

  • [BTM] S. Bradley, A. Hax, T. Magnanti Duality in Linear Programming, Applied Mathematical Programming(1977), chapter 4.
  • [BV] S. Boyd, L. Vandenberghe, Convex Optimization (2004), chapter 5.
  • [Dan] G. B. Dantzig, Linear programming, Operations Research 50 (2002), 42-47.
  • [GW1] 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
  • [PS] C. Papdimitrious and K. Steiglitz, Combinatorial Optimization, Prentice Hall, 1982.
  • [Sch] A. Schrijver, Theory of Linear and Integer Programing, Wiley Interscience, 1986.
  • [Tod] M.J. Todd, The many facets of linear programming, Mathematical Programming 91: 417-436 (2002).

Network Optimization

Intractability

  • [AB] S. Arora and B. Barak, Computational Complexity, Cambridge, 2009.
  • [Eri] J. Erickson, CPS473G: Algorithms, UIUC, chapter 30.
  • [GJ] M. Garey and D.S. Johnson, Computers and Intractability, Freeman, 1979.

Approximation Algorithms

Geometry

  • [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.
  • [Mat] J. Matousek, Lectures on Discrete Geometry, Springer, 2002.

Hashing



page top