A PROBE-based heuristic for graph partitioning

被引：24

作者：

Chardaire, Pierre ^{[1
]}

Barake, Musbah

McKeown, Geoff P.

机构：

[1] Univ E Anglia, Sch Comp Sci, Norwich NR4 7TJ, Norfolk, England

[2] Amer Univ Beirut, Suliman S Olayan Sch Business, Beirut, Lebanon

来源：

IEEE TRANSACTIONS ON COMPUTERS | 2007年 / 56卷 / 12期

关键词：

evolutionary computing; heuristic methods; graph algorithms; graph bisection; graph partitioning;

D O I：

10.1109/TC.2007.70760

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：1707 / 1720

页数：14

共 34 条

[1]

Alpert CJ, 1997, DES AUT CON, P530, DOI 10.1145/266021.266275

[2] RECENT DIRECTIONS IN NETLIST PARTITIONING - A SURVEY [J].

ALPERT, CJ ;

KAHNG, AB .

INTEGRATION-THE VLSI JOURNAL, 1995, 19 (1-2) :1-81

[3] AN APPLICATION OF COMBINATORIAL OPTIMIZATION TO STATISTICAL PHYSICS AND CIRCUIT LAYOUT DESIGN [J].

BARAHONA, F ;

GROTSCHEL, M ;

JUNGER, M ;

REINELT, G .

OPERATIONS RESEARCH, 1988, 36 (03) :493-513

[4]

Barake M, 2004, APPL OPTIM, V86, P19

[5] FAST MULTILEVEL IMPLEMENTATION OF RECURSIVE SPECTRAL BISECTION FOR PARTITIONING UNSTRUCTURED PROBLEMS [J].

BARNARD, ST ;

SIMON, HD .

CONCURRENCY-PRACTICE AND EXPERIENCE, 1994, 6 (02) :101-117

[6] Greedy, prohibition, and reactive heuristics for graph partitioning [J].

Battiti, R ;

Bertossi, AA .

IEEE TRANSACTIONS ON COMPUTERS, 1999, 48 (04) :361-385

[7]

BATTITI R, 1997, P DIMACS WORKSH NETW

[8]

BUI TN, 1993, PROCEEDINGS OF THE SIXTH SIAM CONFERENCE ON PARALLEL PROCESSING FOR SCIENTIFIC COMPUTING, VOLS 1 AND 2, P445

[9]

Bui TN, 1996, IEEE T COMPUT, V45, P841, DOI 10.1109/12.508322

[10] GRAPH BISECTION ALGORITHMS WITH GOOD AVERAGE CASE BEHAVIOR [J].

BUI, TN ;

CHAUDHURI, S ;

LEIGHTON, FT ;

SIPSER, M .

COMBINATORICA, 1987, 7 (02) :171-191

← 1 2 3 4 →