One-Half Approximation Algorithms for the k-Partition Problem

DOI10.1287/opre.40.1.S170zbMath0745.90072OpenAlexW2062134187MaRDI QIDQ3990575

Mallek Khellaf, Thomas A. Feo, Olivier Goldschmidt

Publication date: 28 June 1992

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/opre.40.1.s170

zbMATH Keywords

edge-weighted graph\(k\)-partition problemBottom-up type heuristics

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (9)

On approximating the memory-constrained module allocation problem ⋮ An improved approximation algorithm for the metric maximum clustering problem with given cluster sizes ⋮ An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding ⋮ NP-hardness of \(m\)-dimensional weighted matching problems ⋮ Tabu search and GRASP for the capacitated clustering problem ⋮ Balanced tree partition problems with virtual nodes ⋮ New bounds and algorithms for the transshipment yard scheduling problem ⋮ Approximation algorithms for the metric maximum clustering problem with given cluster sizes. ⋮ Balanced partitions of trees and applications

This page was built for publication: One-Half Approximation Algorithms for the k-Partition Problem