Given a graph with positive integer edge weights one may ask whether there exists an edge cut whose weight is bigger than a given number. This problem is NP-Complete. We present here an approximation scheme in NC which provides tight upper bounds to the proportion of edge cuts whose size is bigger than a given number. Our technique is based on the method to convert randomized algorithms into deterinistic ones, introduced by [Luby, 85 and 88]. The basic idea of those methods is to replace an exponentially large sample space by one of polynomial size. Our work examines the statistical distance of random variables of the small sample space to corresponding variables of the exponentially large space, which is the space of all edge cuts taken equiprobably.
(EN)
