CSE521 - Links and Resources

CSE Home

About Us

Search

Contact Info

Approximation Algorithms

Lecture Notes on Approximation Algorithms, Spring 1998. IBM Research Report RC 21273, September 1998 that you can find on this page.

Randomized Graph Algorithms

• A New Approach to the Minimum Cut Problem, Karger and Stein, 1996.
• A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees, Karger, Klein, and Tarjan, 1995.
• Randomization in Graph Optimization Problems: A Survey, David Karger, 1998.
• David Karger's thesis: Random Sampling in Graph Optimization Problems.
• David Karger's homepage and publications.
• Backwards Analysis of Randomized Geometric Algorithms, Raimund Seidel, 1992
• Size-Estimation Framework with Applications to Transitive Closure and Reachability, Edith Cohen, 1994.

	Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to nchernia]