Seminar in Operations Research

SES #: 1 · TOPICS: MAXCUT; Semidefinite Programming; and the Goemans-Williamson Paper · READINGS: Goemans, Michel X., and David P. Williamson. “Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming.” Journal of the ACM 42, no. 6 (November 1995): 1115-45.

SES #: 2 · TOPICS: Dunagan and Vempala Paper; Storn and Price Paper · READINGS: Dunagan, John, and Santosh Vempala. “A Simple Polynomial-Time Rescaling Algorithm for Solving Linear Programs.” In Proceedings of the 36th Annual Association for Computing Machinery Symposium on Theory of Computing. New York, NY: ACM Press, 2004.

Storn, Rainer, and Kenneth Price. “Differential Evolution - A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces.” Journal of Global Optimization 11 (1997): 341-59.

SES #: 3 · TOPICS: Clarkson Paper; Motwani and Raghavan chapter 9 · READINGS: Clarkson, Kenneth L. “Las Vegas Algorithms for Linear and Integer Programming When the Dimension Is Small.” Journal of the ACM 42, no. 2 (March 1995): 488-99.

Motwani, Rajeev, and Prabhakar Raghavan. Chapter 9 in Randomized Algorithms. Cambridge, UK: Cambridge University Press, 1995. ISBN: 0-521-47465-5.

SES #: 4 · TOPICS: Kalai Paper #1; Kalai Paper #2 · READINGS: Kalai, Gil. “A Subexponential Randomized Simplex Algorithm (Extended Abstract).” In Proceedings of the 24th Annual Association for Computing Machinery Symposium on Theory of Computing. New York, NY: ACM Press, 1992.

Kalai, Gil. “Linear Programming, the Simplex Algorithm and Simple Polytopes.” Jerusalem, Israel: Hebrew University of Jerusalem, May 1997.

SES #: 5 · TOPICS: Solis and Wets Paper; Romeijn Thesis Book · READINGS: Solis, F. J., and R. J-B. Wets. “Minimization by Random Search Techniques.” Mathematical Operations Research 6 (1981): 19-30.

Romeijn, H. Edwin. “Global Optimization by Random Walk Sampling Methods.” Amsterdam: Thesis Publishers, 1992.

SES #: 6 · TOPICS: Zabinsky and Smith Paper · READINGS: Zabinsky, Zelda B., and Robert L. Smith. “Pure Adaptive Search in Global Optimization.” Mathematical Programming 55 (1992): 323-38.

SES #: 7 · TOPICS: Simonovits Paper · READINGS: Simonovits, Miklós. “How to Compute the Volume in High Dimension?” Mathematical Programming B 97 (2003): 337-74.

SES #: 8 · TOPICS: Romeijn and Smith Paper · READINGS: Romeijn, H. Edwin, and Robert L. Smith. “Simulated Annealing for Constrained Global Optimization.” Journal of Global Optimization 5 (1994): 101-26.

SES #: 9 · TOPICS: Bertsimas and Vempala Paper; Zabinsky, Smith, etc. Paper · READINGS: Bertsimas, Dimitris, and Santosh Vempala. “Solving Convex Programs by Random Walks.” In Proceedings of the 34th Annual Association for Computing Machinery Symposium on the Theory of Computing. New York, NY: ACM Press, 2002.

Zabinsky, Zelda B., Robert L. Smith, J. Fred McDonald, H. Edwin Romeijn, and David E. Kaufman. “Improving Hit-and-Run for Global Optimization.” _Journal of Global Optimization _ 3 (1993): 171-92.

SES #: 10 · TOPICS: Zabinsky, Graesser, etc. Paper; Sanjeev Paper · READINGS: Zabinsky, Zelda B., D. L. Graesser, M. E. Tuttle, and G. I. Kim. “Global Optimization of Composite Laminates Using Improving Hit and Run.” In Recent Advances in Global Optimization , edited by Christodoulos A. Floudas and Panos M. Pardalos, 343-68. Princeton University Press, 1992. ISBN: 0-691-08740-7.

Arora, Sanjeev. “Approximation Schemes for NP-hard Geometric Optimization Problems: A Survey.” Mathematical Programming B 97 (2003): 43-69.