A class of bounded approximation algorithms for graph partitioning
From MaRDI portal
Publication:3474493
DOI10.1002/net.3230200205zbMath0696.90074OpenAlexW2033954061MaRDI QIDQ3474493
Publication date: 1990
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.3230200205
heuristicsmatchingweighted graphheuristicGraph partitioningbounded approximation algorithmsequal-sized disjoint subsets
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
Approximation algorithms for multi-dimensional assignment problems with decomposable costs ⋮ An improved approximation algorithm for the metric maximum clustering problem with given cluster sizes ⋮ Iterated maxima search for the maximally diverse grouping problem ⋮ Minimum transversals of maximum matchings as approximate solutions to the bisection problem ⋮ NP-hardness of \(m\)-dimensional weighted matching problems ⋮ Approximation algorithms for maximum dispersion ⋮ Tabu search for graph partitioning ⋮ A three-phase search approach with dynamic population size for solving the maximally diverse grouping problem ⋮ On using learning automata for fast graph partitioning ⋮ The balanced maximally diverse grouping problem with attribute values ⋮ Balanced tree partition problems with virtual nodes ⋮ Truthful Mechanisms for Matching and Clustering in an Ordinal World ⋮ The balanced maximally diverse grouping problem with integer attribute values ⋮ Neighborhood decomposition based variable neighborhood search and tabu search for maximally diverse grouping ⋮ A black-box scatter search for optimization problems with integer variables ⋮ Approximation algorithms for the metric maximum clustering problem with given cluster sizes. ⋮ Generating irregular partitionable data structures ⋮ A new mixed-integer programming formulation for the maximally diverse grouping problem with attribute values ⋮ Solving balanced multi-weighted attribute set partitioning problem with variable neighborhood search ⋮ Balanced partitions of trees and applications ⋮ Approximating the maximum quadratic assignment problem ⋮ Solution of large weighted equicut problems
Cites Work
