Graph Partitioning Using Metaheuristic Techniques
 |
International Journal of Computer Trends and Technology (IJCTT) |  |
| © 2019 by IJCTT Journal | ||
| Volume-67 Issue-10 |
||
| Year of Publication : 2019 | ||
| Authors : Naresh Ghorpade, H. R. Bhapkar | ||
| DOI : 10.14445/22312803/IJCTT-V67I10P109 |
MLA Style:Naresh Ghorpade, H. R. Bhapkar"Graph Partitioning Using Metaheuristic Techniques," International Journal of Computer Trends and Technology 67.10 (2019):51-59.
APA Style Naresh Ghorpade, H. R. Bhapkar. Graph Partitioning Using Metaheuristic Techniques International Journal of Computer Trends and Technology, 67(10),51-59.
Abstract
The graph partitioning problem aims to partition the vertices of graph into a certain number of blocks in such a way that the edge cut is minimized and balance constraint that all blocks must be of the same weight should also be maintained. This paper is dedicated to the application of metaheuristics to the optimization of graph partitioning problem. Numerous adaptations of metaheuristics for partitioning of graphs have been proposed in last twenty years. In this paper State – of – the art methods which focuses on local as well as population-based metaheuristics are analyzed in depth.
Reference
[1] R.T Marler, ?Survey of multi-objective optimization methods for engineering,? Springer, 2004.
[2] Kirkpatrick, S., Gelatt, C.D. and Vecchi, P. M., ?Optimization by simulated annealing,? Science direct, vol. 220, pp. 671-680, 1983.
[3] H. Simon and S. Teng, ?How Good is Recursive Bisection,? SIAMJournal on Scientific Computing, vol.18, no.5, pp. 1436 - 1445, 1997.
[4] R. Banos and C. Gil, ?Multilevel Heuristic Algorithm for Graph Partitioning,? in Proceedings of the European Workshop on Evalutionary Computations in Combinatorial Optimization, pp. 143 – 153, 2003.
[5] R. Banos and C. Gil, ?A Parallel Multilevel Heuristic for Graph Partitioning,? in Journal of Heuristics, Vol. 10, pp. 315 - 336, 2004.
[6] C. Bichot,? Metaheuristic for Graph Bisection,? in Proceedings of the 10th ACM Genetic and Evalutionary Computation Conference, pp. 1801 - 1802, 2009.
[7] V.Cerny, ?A thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm,? Journal of Optimization Theory and Applications, vol. 45, no.1, pp. 41-51, 1985.
[8] Aarts and Korst, ?Simulated annealing and Boltzmann machines,? Wiley Publication, 1989.
[9] D. Johnson, C. Shavon, and c. Aragon, ?Optimization by Simulated Annealing: An Experimental Evaluation, Part – I Graph Partitioning,? Operations Research Society of America, Vol. 37, No. 6, pp. 865 – 892, 1989.
[10] C. Bichot,?A new method, the fusion fission, for the relxed k – wak graph partitioning problem and comparison with some multilevel algorithms,? in Journal of Mathematical Modelling and Algorithms, Vol. 6, No. 3, pp. 319 - 344, 2007.
[11] Goldberg DE., ?Genetic algorithm: search, optimization and machine learning,? Addison Wesley Publishing Company, 1989.
[12] T. N. Bui and B.-R. Moon. Genetic algorithm and graph partitioning. IEEE Transactions on Computers, 45(7):841–855, 1996.
[13] H. Muhlenbein and T. Mahnig. Evolutionary optimization ¨ and the estimation of search distributions with applications to graph bipartitioning. International Journal of Approximate Reasoning, 31(3):157–192, 2002.
[14] A. J. Soper, C. Walshaw, and M. Cross. A combined evolutionary search and multilevel optimisation approach to graph-partitioning. Journal of Global Optimization, 29(2):225–241, 2004.
[15] J. G. Martin. Spectral techniques for graph bisection in genetic algorithms. In Genetic and Evolutionary Computation Conference, pages 1249–1256, 2006.
[16] Glover, F. and Laguna, M., ?Tabu search,? ch.3, ?Modern heuristic techniques for combinatorial problems,? McGraw-Hill Publications, pp 70-150, 1995.
[17] Michel Gendreau and Jean-Yves Potvin, ?Tabu Search?, Handbook of metaheuristics, International Series in Operations Research and Management Science, 146, Springer Science Business Media, 2010.
[18] Rolland, E., Pirkul, H. and Glover, ?Tabu search for graph partitioning,? Annals of Operations Research. Vol. 63 pp.209-232, 2004.
[19] C. Walshaw, ?Multilevel refinement for combinatorial optimization problems‘?. Annals of Operations Research, Vol l31. pp. 325-372, 2006.
[20] P. Galienier, Z. Boujbel, and M. C. Fernandes, An Efficient Memetic Algorithm for Graph Partitioning, in Annals of Operations Research, pp. 1 – 22, 2011.
[21] U, Benlic, and J. K. Hao, ?An Effective Multilevel Memetic Algorithm for Balanced Graph Partitioning,? in 22ndIEEE Conference on Tools with Artificial Intelligence, pp. 121 - 128, 2010.
[22] U, Benlic, and J. K. Hao, ?An Effective Multilevel Tabu Search Approach for Balanced Graph Partitioning,? in Tans. on Computers and Operations Research, Vol. 7, No. 38, pp. 1066 - 1075, 2011.
[23] R. Diekmann and C. Walshaw, ?Shape Optimized Mesh Partitioning and Load Balancing for Parallel Adaptive FEM,? in Journal on Parallel Computing, vol.12, no.26, pp. 1555 - 1581, 2000.In Proc. Internatl. Conference on Parallel and Distributed Systems (ICPADS‘09), pp. 150–157. IEEE Computer Society, 2009.
[24] Henning Meyerhenke, ?Beyond good shapes: Diffusion-based graph partitioning is relaxed cut optimization,? In Proc. 21st International Symposium on Algorithms and Computation (ISAAC‘10). Springer-Verlag, 2010.
[25] CE Bichot,?A metaheuristic based on fusion and fission for partitioning problems,? Parallel and Distributed Processing Symposium, 2006. IPDPS 2006.
[26] CE Bichot,?A new method, the fusion fission, for the relaxed k-way graph partitioning problem, and comparisons with some multilevel algorithms,?Journal of Mathematical Modelling and Algorithms 6 (3), pp. 319-344, 2007
[27] B. K. Panigrahi, Y. Shi, and M.-H. Lim (eds.),? Handbook of Swarm Intelligence,? Series: Adaptation, Learning, and Optimization, Vol 7, Springer-Verlag Berlin Heidelberg, 2011. ISBN 978-3-642-17389-9.
[28] C. Blum and D. Merkle (eds.). Swarm Intelligence – Introduction and Applications. Natural Computing. Springer, Berlin, 2008.
[29] L´aszl´oLov´asz and Mikl´osSimonovits,? Random walks in a convex body and an improved volume algorithm,?Random Struct. Algorithms, Vol.4, No. 4, pp. 359–412, 1993.
[30] C. Ding, X. He, H. Zha, M. Gu, and H. Simon, ?A min-max cut algorithm for graph partitioning and data clustering,? In ICDM, pp. 107–114, 2001.
[31] H. Meyerhenke, B. Monien, S. Schamberger,?Graph Partitioning and Disturbed Diffusion,? Parallel Computing, Vol. 35(10-11) pp. 544-569, 2009.
[32] Henning Meyerhenke, ?Dynamic load balancing for parallel numerical simulations based on repartitioning with disturbed diffusion,?
[33] M. Belal, J. Gaber, H. El-Sayed, and A. Almojel, Swarm Intelligence, In Handbook of Bioinspired Algorithms and Applications. Series: CRC Computer & Information Science. Vol. 7. Chapman & Hall Eds, 2006. ISBN 1-58488-477-5.
[34] C. Blum, Beam-ACO—Hybridizing ant colony optimization with beam search: An application to open shop scheduling, Comput. Oper. Res., Vol. 32, No. 6, pp. 1565–1591, 2005.
[35] P. Balaprakash, M. Birattari, T. Stützle, Z. Yuan, and M. Dorigo, ?Estimation based ant colony optimization algorithms for the probabilistic travelling salesman problem,?. Swarm Intell., 3(3), pp. 223–242, 2009.
[36] P. Korosec, J. Silc and B. Robic, "Mesh Partitioning: A Multilevel Ant-Colony-oOtimization Algorithm," in Parallel and Distributed Processing Symposium, 2003.
[37] K. Taskova, P. Korosec and J. Silc, "A Distributed Multilevel Ant Colonies Approach," Informatica, vol. 32, no. 3, pp. 307-317, 2008.
[38] Comellas, F., Sapena, E., 2006, ?A Multiagent Algorithm for Graph Partitioning. Applications of Evolutionary Computing,? Lecture Notes in Computer Science. Springer, 3907, pp.279-285, 2008
[39] J. Kennedy and R. Eberhart, ?Particle swarm optimization,? in the Proceedings of IEEE International Conference on Neural Networks, Perth, Australia, Vol. 4, pp. 1942-1948, 1995.
[40] S. Gadde, ?Graph partitioning algorithms for minimizing internode communication on a distributed system,? Ph. D Thesis, 2013.
[41] S. D. Kapade, ?Swarm intelligence-based graph partitioning for image segmentation,? 2015.
Keywords
Graph partitioning, Optimization technique, Swarm Intelligence