One-Half Approximation Algorithms for the k-Partition Problem

DOI10.1287/OPRE.40.1.S170MaRDI QIDQ3990575zbMATH OpenOpenAlexFDO

Authors Thomas A. Feo, Olivier Goldschmidt, Mallek Khellaf

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

\(k\)-partition problemedge-weighted graphBottom-up type heuristics

Mathematics Subject Classification ID

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

Recommendations

• A class of bounded approximation algorithms for graph partitioning
• The \(k\)-partitioning problem
• scientific article; zbMATH DE number 2032361
• Approximation algorithms for min-sum \(p\)-clustering

Cited in

(17)

• Sum-max graph partitioning problem
• Feasible and infeasible region search for the maximally diverse grouping problem
• An improved approximation algorithm for the metric maximum clustering problem with given cluster sizes
• A class of bounded approximation algorithms for graph partitioning
• Tabu search and GRASP for the capacitated clustering problem
• On the sum-max graph partitioning problem
• On approximating the memory-constrained module allocation problem
• Approximation Algorithms for Some Graph Partitioning Problems
• Direct graph \(k\)-partitioning with a Kernighan-Lin like heuristic
• An efficient heuristic for the \(k\)-partitioning problem
• Approximation algorithms for the metric maximum clustering problem with given cluster sizes.
• Approximating element-weighted vertex deletion problems for the complete k-partite property
• NP-hardness of \(m\)-dimensional weighted matching problems
• An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding
• New bounds and algorithms for the transshipment yard scheduling problem
• Balanced tree partition problems with virtual nodes
• Balanced partitions of trees and applications

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3990575)