Examinando por Autor "Resende, Mauricio G.C."

Seleccione resultados tecleando las primeras letras
Mostrando 1 - 1 de 1
  • Miniatura
    Ítem
    Two-phase GRASP for the Multi-Constraint Graph Partitioning problem
    (Elsevier, 2025-04) Herrán, Alberto; Colmenar, J. Manuel; Resende, Mauricio G.C.
    The Multi-Constraint Graph Partitioning (MCGP) problem seeks a partition of the node set of a graph into a fixed number of clusters such that each cluster satisfies a collection of node-weight constraints and the total cost of the edges whose end nodes are in the same cluster is minimized. In this paper we propose a two-phase reactive GRASP heuristic to find near-optimal solutions to the MCGP problem. Our proposal is able to reach all the best known results for state-of-the-art instances, obtaining all the certified optimum values while spending only a fraction of the time in relation to the previous methods. To reach these results we have implemented an efficient computation method applied in the improvement phase. Besides, we have created a new set of larger instances for the MCGP problem and provided detailed results for future comparisons