One-Half Approximation Algorithms for the k-Partition Problem

The k-partition problem seeks to cluster the vertices of an edge-weighted graph, G = (V, E), into k sets of |V|/k vertices each, such that the total weight of the edges having both endpoints in the same cluster is maximized. Bottom-up type heuristics based on matchings are presented for this problem. These heuristics are shown to yield solutions that are at least one-half the weight of the optimal solution for k equal to |V|/3 and |V|/4.