Courses:

Behavior of Algorithms >> Content Detail



Study Materials



Readings

Amazon logo When you click the Amazon logo to the left of any citation and purchase the book (or other media) from Amazon.com, MIT OpenCourseWare will receive up to 10% of this purchase and any other purchases you make during that visit. This will not increase the cost of your purchase. Links provided are to the US Amazon site, but you can also support OCW through Amazon sites in other regions. Learn more.
LEC #TOPICSREADINGS
1Introduction
2The Condition NumberDemmel, James W. "The Probability that a Numerical Analysis Problem is Difficult." Mathematics of Computation 50, no. 182 (April 1988): 449-480.

Edelman, Alan. "Eigenvalues and Condition Numbers of Random Matrices." SIAM J. Matrix Anal. Appl 9, no. 4 (1988): 543-560.

Edelman, A. "Eigenvalues and Condition Numbers of Random Matrices." 1989. Ph.D. Thesis. (PDF - 1.3 MB)
3The Largest Singular Value of a MatrixSzarek, Stanislaw J. "Spaces with Large Distance to l^n_inf and Random Matrices." American Journal of Mathematics 112, no. 6 (Dec 1990): 899-942.

Geman, Stuart. "A Limit Theorem for the Norm of Random Matrices." Annals of Probability 8, no. 2 (April 1980): 252-261.

Szarek, Stanislaw J. "Condition Numbers of Random Matrices." Journal of Complexity 7, no. 2 (June 1991): 131-149.

Edelman, Alan. "Eigenvalues and Condition Numbers of Random Matrices." SIAM J. Matrix Anal. Appl 9, no. 4 (1988): 543-560.

Kahn, Jeff, Janos Komlos, and Endre Szemeredi. "On the Probability that a Random +/- 1 Matrix is Singular." Journal of the American Mathematical Society 8, no. 1 (January 1955): 223-240.
4Gaussian Elimination without PivotingGolub, Gene H., and Charles F. Van Loan. "Theorem 3.4.3." Chapter 3 in Matrix Compuations. 3rd ed. Baltimore and London: The Johns Hopkins University Press, November 1, 1996, section 4.

Wilkinson, J. H. "Error Analysis of Direct Methods of Matrix Inversion." Journal of the ACM 8, no. 3 (July 1961): 281-330.
5Smoothed Analysis of Gaussian Elimination without Pivoting
6Growth Factors of Partial and Complete Pivoting

Speeding up GE of Graphs with low Bandwidth or Small Separators
Wilkinson, J. H. "Error Analysis of Direct Methods of Matrix Inversion." Journal of the ACM 8, no. 3 (July 1961): 281-330.

Turner, Jonathan S. "On the Probable Performance of Heuristics for Bandwidth Minimization." SIAM Journal on Computing 15, no. 2 (May 1986).

Feige, Uri, and Robert Krauthgamer. "Smoothed Analysis." In Improved Performance Guarantees for Bandwidth Minimization Heuristics." Unpublished manuscript, 1998.

"Generalized Nested Dissection." SIAM Journal on Numerical Analysis 16 (1979): 346-358.
7Spectral Partitioning Introduced"Spectral Partitioning Works: Planar Graphs and Finite-Element Meshes." Proceedings of the 35th Annual IEEE Conference on Foundations of Computer Science. 1996, pp. 96-105.
8Spectral Partitioning of Planar Graphs"Spectral Partitioning Works: Planar Graphs and Finite-Element Meshes." Proceedings of the 35th Annual IEEE Conference on Foundations of Computer Science. 1996, pp. 96-105.

Proof of Koebe's embedding theorem lecture notes from Applied Extremal Combinatorics.
9Spectral Paritioning of Well-Shaped Meshes and Nearest Neighbor Graphs

Turner's Theorem for Bandwidth of Semi-Random Graphs
Miller, Gary L., Shang-Hua Teng, William Thurston, and Stephen A. Vavasis. "Separators for Sphere-Packings and Nearest Neighbor Graphs." Journal of the ACM 44, no. 1 (January 1997): 1-29.

———. "Geometric Separators for Finite Element Meshes." Siam Journal on Scientific Computing 19, no. 2 (March 1998): 364-386.

Turner, Jonathan S. "On the Probable Performance of Heuristics for Bandwidth Minimization." SIAM Journal on Computing 15, no. 2 (May 1986).
10Smoothed Analysis and Monotone Adversaries for Bandwidth and Graph Bisection

McSherry's Spectral Bisection Algorithm
Feige, Uri, and Joe Kilian. "Heuristics for Semirandom Graph Problems." Journal of Computer and System Sciences.

———. "Heuristics for Finding Large Independent Sets, with Applications to Coloring Semi-Random Graphs." Proceedings of 39th FOCS. 1998, pp. 674-683. Available at Uri Feige's homepage.

Feige, Uri, R. Krauthgamer. "Improved Performance Guarantees for Bandwidth Minimization Heuristics." Unpublished manuscript, November 1998. Available at Robert Krauthgamer's homepage.

Boppana, Ravi . "Eigenvalues and Graph Bisection: an Average-Case Analysis." Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science, pages 280-285, IEEE Computer Society Press, 1987.

Johnson, D. S., C. R. Aragon, L. A. McGeoch, and C. Shevon. "Optimization by Simulated Annealing: an Experimental Evaluation. Part I, Graph Partitioning." Operations Research 37, no. 6 (1989): 865-892.

"Spectral Partitioning of Random Graphs." 42nd IEEE Symposium on Foundations of Computer Science Proceedings: October 14--17, 2001. Las Vegas, Nevada, USA: IEEE Computer Society Press, 2001, pp. 529-537. Frank McSherry's analysis of a spectral partitioning algorithm for the planted bisection model.
11Introduction to Linear Programming

von Neumann's Algorithm, Primal and Dual Simplex Methods

Duality
Epelman, Marina, and Rob Freund. "Condition Number Complexity of an Elementary Algorithm for Resolving a Conic Linear System." (PDF) (Courtesy of Marina Epelman and other students from Behavior of Algorithms. Used with permission.)
12Strong Duality Theorem of Linear Programming

Renegar's Condition Numbers
Renegar, James. "Incorporating Condition Measures into the Complexity Theory of Linear Programming." SIAM Journal on Optimization 5 (1995): 506-524.
13Analysis of von Neumann's AlgorithmEpelman, Marina, and Rob Freund. "Condition Number Complexity of an Elementary Algorithm for Resolving a Conic Linear System." (PDF) (Courtesy of Marina Epelman and other students from Behavior of Algorithms. Used with permission.)

Dunagan, John D, Daniel A. Spielman, and Shang-Hua Teng. "Smoothed Analysis of Renegar's Condition Number for Linear Programming."
14Worst-Case Complexity of the Simplex MethodAmazon logo Amenta, Nina, and Gunter Ziegler. "Deformed Products and Maximal Shadows of Polytopes." Advances in Discrete and Computational Geometry. Edited by B. Chazelle, J. E. Goodman, R. Pollack. Vol. 223, Contemporary Mathematics. Providence, R.I.: Amer. Math. Soc., 1999, pp. 57-90. ISBN: 0821806742.

Ziegler, Günter M. Lectures on Polytopes. New York: Springer-Verlag, 1995.
15The Expected Number of Facets of the Convex Hull of Gaussian Random Points in the PlaneUber die convexe hulle von is zufallig gewahlten punkten, I and II. Z. Whar. 2, 75-84; 3, 138-148. (1963; 1964).
16The Expected Number of Facets of the Convex Hull of Gaussian Random Points in the Plane (cont.)Uber die convexe hulle von is zufallig gewahlten punkten, I and II. Z. Whar. 2, 75-84; 3, 138-148. (1963; 1964).
17The Expected Number of Facets of the Shadow of a Polytope Given by Gaussian Random ConstraintsSpielman, Daniel A, Shang-Hua Teng. "Smoothed Analysis: Why The Simplex Algorithm Usually Takes Polynomial Time."
18The Expected Number of Facets of the Shadow of a polytope Given by Gaussian Random Constraints: Distance BoundSpielman (cont.)
19The Expected Number of Facets of the Shadow of a Polytope Given by Gaussian Random Constraints: Angle Bound and Overview of Phase 1Spielman (cont.)

 








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