loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
A PROBE-Based Heuristic for Graph Partitioning
December 2007 (vol. 56 no. 12)
pp. 1707-1720
ASCII Text
x 
 
Pierre Chardaire, Musbah Barake, Geoff P. McKeown, "A PROBE-Based Heuristic for Graph Partitioning," IEEE Transactions on Computers, vol. 56, no. 12, pp. 1707-1720, December, 2007.
 
 
BibTex
x
 
@article{ 10.1109/TC.2007.70760,
author = {Pierre Chardaire and Musbah Barake and Geoff P. McKeown},
title = {A PROBE-Based Heuristic for Graph Partitioning},
journal ={IEEE Transactions on Computers},
volume = {56},
number = {12},
issn = {0018-9340},
year = {2007},
pages = {1707-1720},
doi = {http://doi.ieeecomputersociety.org/10.1109/TC.2007.70760},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - JOUR
JO - IEEE Transactions on Computers
TI - A PROBE-Based Heuristic for Graph Partitioning
IS - 12
SN - 0018-9340
SP1707
EP1720
EPD - 1707-1720
A1 - Pierre Chardaire,
A1 - Musbah Barake,
A1 - Geoff P. McKeown,
PY - 2007
KW - Evolutionary computing
KW - heuristic methods
KW - graph algorithms
KW - graph bisection
KW - graph partitioning.
VL - 56
JA - IEEE Transactions on Computers
ER -
 
A new heuristic algorithm, PROBE BA, based onthe recently introduced metaheuristic paradigm PROBE (PopulationReinforced Optimization Based Exploration) is proposedfor solving the Graph Partitioning Problem. The "exploration"part of PROBE BA is implemented using the Differential-Greedyalgorithm of Battiti and Bertossi and a modification of theKernighan and Lin algorithm at the heart of Bui and Moon'sGenetic Algorithm, BFS GBA. Experiments are used to investigateproperties of PROBE and show that PROBE BA comparesfavourably with other solution methods based on Genetic Algorithms,Randomized Reactive Tabu Search, or more specializedmultilevel partitioning techniques. In addition, PROBE BA findsnew best cut values for 10 of the 34 instances in Walshaw's GraphPartitioning Archive.

[1] T.N. Bui and C. Jones, “A Heuristic for Reducing Fill in Sparse Matrix Factorization,” Proc. Sixth SIAM Conf. Parallel Processing for Scientific Computing (PPSC '92), pp. 445-452, 1993.
[2] C. Alpert and A. Kahng, “Recent Directions in Netlist Partitioning: A Survey,” Integration—The VLSI J., vol. 19, nos. 1-2, pp. 1-81, 1995.
[3] F.M. Johannes, “Partitioning of VLSI Circuits and Systems,” Proc. 33rd Design Automation Conf., pp. 83-87, 1996.
[4] G.C. Fox, “A Review of Automatic Load Balancing an Decomposition Methods for the Hypercube,” Numerical Algorithms for Modern Parallel Computer Architectures, M. Schultz, ed., Springer, pp. 63-76, 1988.
[5] L. Sanchis, “Multiple-Way Network Partitioning,” IEEE Trans. Computers, vol. 38, pp. 62-81, 1989.
[6] H.D. Simon, “Partitioning of Unstructured Problems for Parallel Processing,” Computing Systems in Eng., vol. 2, pp. 135-148, 1991.
[7] J.R. Gilbert, G.L. Miller, and S.H. Temg, “Geometric Mesh Partitioning: Implementation and Experiments,” Proc. Ninth Int'l Parallel Processing Symp. (IPPS '95), 1995.
[8] B. Hendrickson and R. Leland, “An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations,” SIAM J. Scientific Computing, vol. 16, no. 2, pp. 452-469, 1995.
[9] C. Ding, H. Xiaofeng, Z. Hongyuan, G. Ming, and A. Simon, “Min-Max Cut Algorithm for Graph Partitioning and Data Clustering,” Proc. First IEEE Int'l Conf. Data Mining, pp. 107-114, 2001.
[10] A. Dunlop and B. Kernighan, “A Procedure for Placement of Standard-Cell VLSI Circuits,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 1, pp. 92-98, 1985.
[11] F. Barahona, M. Grötchel, M. Jünger, and G. Reinelt, “Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design,” Operations Research, vol. 36, pp. 493-513, 1988.
[12] B.W. Kernighan and S. Lin, “An Efficient Heuristic Procedure for Partition Graphs,” Bell Systems Technical J., vol. 49, pp. 291-307, Feb. 1970.
[13] C. Fiduccia and R. Mattheyses, “A Linear Time Heuristics for Improving Network Partitions,” Proc. 29th ACM/IEEE Design Automation Conf., pp. 175-181, 1982.
[14] M.D. Garey, D.S. Johnson, and L. Stockmeyer, “Some Simplified NP-Complete Graph Problems,” Theoretical Computer Science, vol. 1, pp. 237-267, 1976.
[15] D.S. Johnson, C.R. Aragon, L.A. McGeoch, and C. Schevon, “Optimization by Simulated Annealing: An Experimental Evaluation,” Part I, Graph Partitioning, Operations Research, vol. 37, pp.865-892, 1989.
[16] M. Dell'Amico and F. Maffioli, “A New Tabu Search Approach to the 0-1 Equicut Problem,” Meta-Heuristics 1995: The State of the Art, pp. 361-377, Kluwer Academic, 1996.
[17] E. Rolland, H. Pirkul, and F. Glover, “Tabu Search for Graph Partitioning,” Annals of Operational Research, vol. 63, pp. 209-232, 1996.
[18] R. Battiti and A. Bertossi, “Greedy, Prohibition and Reactive Heuristics for Graph Partitioning,” IEEE Trans. Computers, vol. 48, pp. 361-385, 1999.
[19] T.N. Bui and B.R. Moon, “Genetic Algorithm and Graph Partitioning,” IEEE Trans. Computers, vol. 45, pp. 841-855, 1996.
[20] A.G. Steenbeek, E. Marchiori, and A.E. Eiben, “Finding Balanced Graph Bipartitions Using a Hybrid Genetic Algorithm,” Proc. IEEE Int'l Conf. Evolutionary Computation (ICEC '98), pp. 90-95, 1998.
[21] M. Laguna, T.A. Feo, and H.C. Elrold, “Adaptive Search Procedure for the Two-Partition Problem,” Operations Research, vol. 42, pp. 677-687, 1994.
[22] S.T. Barnard and H.D. Simon, “Fast Multilevel Implementation of Recursive Spectral Bisection for Partitioning Unstructured Problems,” Concurrency: Practice and Experience, vol. 6, no. 2, pp. 101-117, 1994.
[23] G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, “Multilevel Hypergraph Partitioning: Application in VLSI Domain,” Proc. 34th Design Automation Conf., pp. 526-529, 1997.
[24] C.J. Alpert, J.-H. Huang, and A.B. Kahng, “Multilevel Circuit Partitioning,” Proc. 34th Design Automation Conf., pp. 530-533, 1997.
[25] Y.G. Saab, “A New 2-Way Multi-Level Partitioning Algorithm,” VLSI Design J., vol. 11, no. 3, pp. 301-310, 2000.
[26] Y.G. Saab, “An Effective Multilevel Algorithm for Bisecting Graphs and Hypergraphs,” IEEE Trans. Computers, vol. 53, no. 6, pp. 641-652, June 2004.
[27] C. Walshaw, “Multilevel Refinement for Combinatorial Optimisation Problems,” Annals of Operations Research, no. 131, pp. 325-372, 2004.
[28] R. Battiti and A. Bertossi, “Differential Greedy for the 0-1 Equicut Problem,” Proc. DIMACS Workshop Network Design: Connectivity and Facilities Location, D.Z. Du and P.M. Pardalos, eds., 1997.
[29] M. Barake, P. Chardaire, and G.P. McKeown, “The PROBE Metaheuristic for the Multiconstraint Knapsack Problem,” Metaheuritics, M.G.C. Resende and J.P. de Sousa, eds., pp. 19-36, Springer, 2004.
[30] M. Zbigniew, Genetic Algorithms + Data Structures = Evolution Programs. Springer, 1996.
[31] T.N. Bui, S. Chaudhuri, F.T. Leighton, and M. Sipser, “Graph Bisection Algorithms with Good Average Case Behavior,” Combinatorica, vol. 7, no. 2, pp. 171-191, 1987.
[32] I.S. Duff, R.G. Grimes, and J.G. Lewis, “Sparse Matrix Test Problems,” ACM Trans. Math. Software, vol. 15, no. 1, pp. 1-14, 1989.
[33] A.J. Soper, C. Walshaw, and M. Cross, “A Combined Evolutionary Search and Multilevel Optimisation Approach to Graph Partitioning,” J. Global Optimization, vol. 29, no. 2, pp. 225-241, 2004.
[34] C. Jones, “Vertex and Edge Partitions of Graphs,” PhD dissertation, Pennsylvania State Univ., 1992.

Index Terms:
Evolutionary computing, heuristic methods, graph algorithms, graph bisection, graph partitioning.
Citation:
Pierre Chardaire, Musbah Barake, Geoff P. McKeown, "A PROBE-Based Heuristic for Graph Partitioning," IEEE Transactions on Computers, vol. 56, no. 12, pp. 1707-1720, June 2007, doi:10.1109/TC.2007.70760
Usage of this product signifies your acceptance of the Terms of Use.