A PROBE-based heuristic for graph partitioning

Pierre Chardaire; Musbah Barake; Geoff P. McKeown

doi:10.1109/TC.2007.70760

A PROBE-based heuristic for graph partitioning

Pierre Chardaire, Musbah Barake, Geoff P. McKeown

School of Computing Sciences

Research output: Contribution to journal › Article › peer-review

34 Citations (Scopus)

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.

Original language	English
Pages (from-to)	1701-1720
Number of pages	20
Journal	IEEE Transactions on Computers
Volume	56
Issue number	12
DOIs	https://doi.org/10.1109/TC.2007.70760
Publication status	Published - 2007

Access to Document

10.1109/TC.2007.70760

Cite this

@article{81119da142c7479cb8f5b316973216a3,

title = "A PROBE-based heuristic for graph partitioning",

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.",

author = "Pierre Chardaire and Musbah Barake and McKeown, {Geoff P.}",

year = "2007",

doi = "10.1109/TC.2007.70760",

language = "English",

volume = "56",

pages = "1701--1720",

journal = "IEEE Transactions on Computers",

issn = "0018-9340",

publisher = "The Institute of Electrical and Electronics Engineers (IEEE)",

number = "12",

}

TY - JOUR

T1 - A PROBE-based heuristic for graph partitioning

AU - Chardaire, Pierre

AU - Barake, Musbah

AU - McKeown, Geoff P.

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

U2 - 10.1109/TC.2007.70760

DO - 10.1109/TC.2007.70760

M3 - Article

VL - 56

SP - 1701

EP - 1720

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

SN - 0018-9340

IS - 12

ER -