One-Half Approximation Algorithms for the k-Partition Problem
- 1 February 1992
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 40 (1-suppleme) , S170-S173
- https://doi.org/10.1287/opre.40.1.s170
Abstract
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.Keywords
This publication has 0 references indexed in Scilit: