One-Half Approximation Algorithms for the k-Partition Problem

Thomas Feo, Olivier Goldschmidt and Mallek Khellaf
Additional contact information
Thomas Feo: The University of Texas at Austin, Austin, Texas
Olivier Goldschmidt: The University of Texas at Austin, Austin, Texas
Mallek Khellaf: British Telecom Tymnet, Paris, France

Operations Research, 1992, vol. 40, issue 1-supplement-1, S170-S173

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: networks/graphs; heuristics: approximation algorithms for k-partitions (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.1.S170 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:40:y:1992:i:1-supplement-1:p:s170-s173

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().