203	1998	Jarmo Rantakokko	jarmo@tdb.uu.se	A local refinement algorithm for data partitioning

		Abstract

A local refinement method for data partitioning has been
constructed. The method balances the workload and minimizes locally
the number of edge-cuts. If the initial partitioning is globally good
the algorithm converges rapidly with good
results. Moreover, the arithmetic complexity of an iteration is very
low. The method is well suited for refinement in multilevel
partitioning where the intermediate partitions 
are near optimal but slightly unbalanced. It is also useful for
improvement of global partitioning methods and repartitioning in dynamic 
problems where the workload changes slightly. The algorithm has been
compared with corresponding methods in Chaco and Metis in
the context of multilevel partitioning. The cost of carrying out the
partitioning with our method is lower than in Chaco and of the
same order as in Metis, and still the quality of the
partitioning is comparable and in some cases even better.