Courses:

Advanced Algorithms >> Content Detail



Study Materials



Readings

Amazon logo Help support MIT OpenCourseWare by shopping at Amazon.com! MIT OpenCourseWare offers direct links to Amazon.com to purchase the books cited in this course. Click on the book titles and purchase the book from Amazon.com, and MIT OpenCourseWare will receive up to 10% of all purchases you make. Your support will enable MIT to continue offering open access to MIT courses.

There is no textbook required for the course. Lecture notes are available for the current term as well as selected lecture notes from a previous term. Reference textbooks for each topic are listed in the table below.

TOPICSREADINGS
Linear ProgrammingSchrijver, A. Theory of Linear and Integer Programming . Chichester: John Wiley & Sons, 1998. ISBN: 0471982326.

For the Ellipsoid, 3 references are (the latter 2 contain a few mistakes):

Groetschel, M., L. Lovasz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Berlin, New York: Springer-Verlag, 1993, chapter 3. ISBN: 0387567402. [The standard reference on the ellipsoid. The most complete and precise description.]

Chvatal, V. Linear Programming. New York: W. H. Freeman & Company, 1983, appendix. ISBN: 0716715872. [An easy to read description without all the details.]

Korte, B. H., and J. Vygen. Combinatorial Optimization. Berlin, Heidelberg, New York: Springer-Verlag, 2002, chapter 4. ISBN: 3540431543. [A detailed description.]

For Interior-point Algorithms, a good reference is:

Roos, C., T. Terlaky, and J. -Ph. Vial. Theory and Algorithms for Linear Optimization: An Interior Point Approach. Chichester: John Wiley & Sons, 1997. ASIN: 0471956767.
Network FlowsAhuja, R. K., T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Englewood Cliffs, NJ: Prentice Hall, 1993. ISBN: 013617549X.
Data StructuresFor both Splay Trees and Dynamic Trees:

Sleator, and Tarjan. "Self-adjusting Binary Search Trees." Journal of the ACM 32, no. 3 (July, 1985): 652-686. ISSN: 0004-5411.
Approximation AlgorithmsVazirani, V. Approximation Algorithms. Berlin: Springer-Verlag, 2001. ISBN: 3540653678.

Hochbaum, D., ed. Approximation Algorithms for NP-Hard Problems. Boston: PWS Publishing Company, 1997. ISBN: 0534949681.

Sanjeev Arora's Euclidean TSP paper. Journal of the ACM 45, no. 5 (September, 1998). New York, NY, USA: ACM Press. ISSN: 0004-5411.
Number-Theoretic AlgorithmsLov'asz, L. "An Algorithmic Theory of Numbers, Graphs, and Convexity." In CBMS Regional Conference Series in Applied Mathematics (SIAM, 1986). Philadelphia, PA: Society for Industrial and Applied Mathematics, 1986. ISBN: 0898712033.

Bach, E., and J. Shallit. Algorithmic Number Theory. Vol. 1. Cambridge, MA: MIT Press, August 26, 1996. ISBN: 0262024055.

 








© 2010-2021 OpenCollege.com, All Rights Reserved.
Open College is a service mark of AmeriCareers LLC.