Edge-set reduction to efficiently solve the graph partitioning problem with the genetic algorithm
The graph partitioning problem (GPP) is among the most challenging models in optimization. Because of its NP-hardness, the researchers directed their interest towards approximate methods such as the genetic algorithms (GA). The edge-based GA has shown promising results when solving GPP. However, for big dense instances, the size of the encoding representation becomes too huge and affects GA's efficiency. In this paper, we investigate the impact of modifying the size of the chromosomes on the edge based GA by reducing the GPP edge set. We study the GA performance with different levels of reductions, and we report the obtained results.
Code (0)
등록된 구현이 없습니다.
Tasks
graph partitioningMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Preconditioned Spectral Clustering for Stochastic Block Partition Streaming Graph Challenge
Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) is demonstrated to efficiently solve eigenvalue problems for graph Laplacians that appear in spectral clustering. For static graph partitioning, 10-20 iter…
Clusteringgraph partitioningHypergraph Partitioning using Tensor Eigenvalue Decomposition
Hypergraphs have gained increasing attention in the machine learning community lately due to their superiority over graphs in capturing super-dyadic interactions among entities. In this work, we propose a novel approach …
graph partitioninghypergraph partitioningA Graph-Partitioning Based Continuous Optimization Approach to Semi-supervised Clustering Problems
Semi-supervised clustering is a basic problem in various applications. Most existing methods require knowledge of the ideal cluster number, which is often difficult to obtain in practice. Besides, satisfying the must-lin…
Clusteringgraph partitioningArmada: Memory-Efficient Distributed Training of Large-Scale Graph Neural Networks
We study distributed training of Graph Neural Networks (GNNs) on billion-scale graphs that are partitioned across machines. Efficient training in this setting relies on min-edge-cut partitioning algorithms, which minimiz…
Energy-Efficient Offloading in Delay-Constrained Massive MIMO Enabled Edge Network Using Data Partitioning
We study a wireless edge-computing system which allows multiple users to simultaneously offload computation-intensive tasks to multiple massive-MIMO access points, each with a collocated multi-access edge computing (MEC)…
CPUEdge-computing