BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR93-201
ENTRY:: January 20, 1995
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: Parallel Max Cut Approximations
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Pantziou, Grammati E.
AUTHOR:: Spirakis, Paul G.
AUTHOR:: Zaroliagis, Christos D.
NOTE:: The 'January' in DATE is an arbitrary placeholder.
DATE:: January 1993
ABSTRACT::
	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
algorithm 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 methods to convert randomized parallel algorithms into
deterministic ones introduced by Karp and Wigderson. The basic idea of
those methods is to replace an exponentially large sample space by one
of polynomial size. In this work, we prove the interesting result that
the statistical distance of random variables of the small sample space
is bigger than the statistical distance of corresponding variables of
the exponentially large space, which is the space of all edge cuts
taken equiprobably.
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR93-201.pdf
END::