BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-95-1541
       ENTRY:: February 07, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Random Sampling in Graph Optimization Problems
        TYPE:: Thesis
        TYPE:: Technical Report
      AUTHOR:: Karger, David R.
        DATE:: February 1995
       PAGES:: 250
    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.
       NOTES:: [Adminitrivia V1/Prg/19950207]
         END:: STAN//CS-TR-95-1541