Path Optimization and Near-Greedy Analysis for Graph Partitioning:
		An Empirical Study

	Jonathan Berry   	Mark Goldberg
 	  Rensselaer Polytechnice Institiute


Abstract:

This paper presents the results of an experimental study of 
graph partitioning.  We describe a new heuristic technique,
path optimization, and its application to two
variations of graph partitioning: the max-cut problem and
the min-quotient-cut problem. We  present the results
of computational comparisons between this technique and
the Kernighan-Lin algorithm, the simulated annealing 
algorithm, a flow-based algorithm, a
multilevel spectral algorithm,
and the recent 0.878-approximation algorithm (for max-cut). 
The experiments were conducted on two classes of graphs
that have become standard for such tests: random and random geometric.
They show that for both classes of inputs and 
both variations of the problem, the new heuristic is
competitive with the other algorithms, and  
holds a advantage for min-quotient-cut when applied to
very large, sparse geometric graphs (10,000 - 100,000 vertices,
average degree <=  10.

In the last part of the paper, we  describe an approach to analyzing
graph partitioning algorithms from the statistical point of view.
Every partitioning of a graph is viewed as a result achieved by a
``near greedy'' partitioning algorithm. The experiments show that 
for ``good'' partitionings, the number of non-greedy steps needed to
obtain them is quite small; moreover, it is
``statistically'' smaller for better partitionings.
This led us to conjecture that there exists an ``optimal''
distribution  of the non-greedy steps that 0 the classes
of graphs that we studied.

contact Jon Berry at berryj@cs.rpi.edu for a copy of the paper