Institution: Stanford University, Department of Computer Science

Title: Random Sampling in Graph Optimization Problems

Author: Karger, David R.

Date: February 1995

Abstract: The representative random sample is a central concept of statistics. It is often possible to gather a great deal of information about a large population by examining a small sample randomly drawn from it. This approach has obvious advantages in reducing the investigator's work, both in gathering and in analyzing the data. We apply the concept of a representative sample to combinatorial optimization. Our focus is optimization problems on undirected graphs. Highlights of our results include: The first (randomized) linear time minimum spanning tree algorithm; A (randomized) minimum cut algorithm with running time roughly O(n^2) as compared to previous roughly O(n^3) time bounds, as well as the first algorithm for finding all approximately minimal cuts and multiway cuts; An efficient parallelization of the minimum cut algorithm, providing the first parallel (RNC) algorithm for minimum cuts; A derandomization finding minimum cut in NC; Provably accurate approximations to network reliability; Very fast approximation algorithms for minimum cuts, s-t minimum cuts, and maximum flows; Significantly improved polynomial-time approximation bounds for network design problems; For coloring 3-colorable graphs, improvements in the approximation bounds from O(n^{3/8}) to O(n^{1/4}); An analysis of random sampling in Matroids.

http://i.stanford.edu/pub/cstr/reports/cs/tr/95/1541/CS-TR-95-1541.pdf