Processing...

### Path optimization and near-greedy analysis for graph partitioning: an empirical study

**1995-04-13**

9504213 | math.CO

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, the FLOW-lagorithm the multilevel algorithm, and
teh recent 0.878-approximation algorithm. 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
an advantage for min_quotient_cut when applied to very large, sparse geometric
graphs. 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 gready"
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
characterize the classes of graphs that we studied.

**Login to like/save this paper, take notes and configure your recommendations**