A PROBE-Based Heuristic for Graph Partitioning
- 29 October 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 56 (12), 1707-1720
- https://doi.org/10.1109/tc.2007.70760
Abstract
A new heuristic algorithm, PROBE_BA, which is based on the recently introduced metaheuristic paradigm population- reinforced optimization-based exploration (PROBE), is proposed for solving the Graph Partitioning Problem. The "exploration" part of PROBE_BA is implemented by using the differential-greedy algorithm of Battiti and Bertossi and a modification of the Kernighan-Lin algorithm at the heart of Bui and Moon's genetic algorithm BFS _GBA. Experiments are used to investigate properties of PROBE and show that PROBE_BA compares favorably with other solution methods based on genetic algorithms, randomized reactive tabu search, or more specialized multilevel partitioning techniques. In addition, PROBE_BA finds new best cut values for 10 of the 34 instances in Walshaw's graph partitioning archive.Keywords
This publication has 30 references indexed in Scilit:
- Multilevel Hypergraph Partitioning: Application In Vlsi DomainPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Multilevel Circuit PartitioningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Multilevel Refinement for Combinatorial Optimisation ProblemsAnnals of Operations Research, 2004
- An effective multilevel algorithm for bisecting graphs and hypergraphsIEEE Transactions on Computers, 2004
- Finding balanced graph bi-partitions using a hybrid genetic algorithmPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Geometric mesh partitioning: implementation and experimentsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A New 2-way Multi-level Partitioning AlgorithmVLSI Design, 2000
- A Greedy Randomized Adaptive Search Procedure for the Two-Partition ProblemOperations Research, 1994
- Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problemsConcurrency: Practice and Experience, 1994
- Partitioning of unstructured problems for parallel processingComputing Systems in Engineering, 1991