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

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

1995-04-13

arxiv.org/abs/math/9504213v1

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Path optimization and near-greedy analysis for graph partitioning: an empirical study does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Path optimization and near-greedy analysis for graph partitioning: an empirical study, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Path optimization and near-greedy analysis for graph partitioning: an empirical study will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-542813