An Improved Driving Training-Based Optimization Algorithm for the Minimum Gap Graph Connected Partition Problem
DOI:
https://doi.org/10.54536/ajiri.v3i4.2530Keywords:
Connected Graph Partition, Metaheuristic Algorithms, Minimum Gap Partition, Optimization AlgorithmsAbstract
In this paper, we consider the minimum gap partition problem in an undirected connected graph with nonnegative vertex weights. This problem involves in dividing the given graph into a specified number of connected subgraphs such that the total difference between the largest and the smallest vertex weights in each subgraph is minimized. Namely, let G = (V, E, W) be a given undirected connected graph with vertex set V , edge set E, and nonnegative vertex weight function W : V → R+, and let k ≥ 2 be a given positive integer. The minimum gap partition problem consists of constructing a partition P = {V1, V2, . . . , Vk} of non-empty and pairwise disjoint subsets of V such that each vertex set Vi, i = 1, 2, . . . , k, induces a connected subgraph G[Vi] of G. The objective of the problem is to find such a partition of V that minimizes the total difference 1≤i≤k maxv∈Viw(v) − minv∈Viw(v). This problem, as many other variants of graph partition problems, is known to be NP-hard problem. We designed an efficient metaheuristic algorithm for finding approximate solution of large-scale instances of this problem. The quality of the proposed algorithm is assessed comparing with the previous algorithms proposed for the problem.
Downloads
References
Albornoz, V. M., Véliz, M. I., Ortega, R., & Ortíz-Araya, V. (2020). Integrated versus hierarchical approach for zone delineation and crop planning under uncertainty. Annals of Operations Research, 286, 617-634.
Apollonio, N., Lari, I., Ricca, F., Simeone, B., & Puerto, J. (2008). Polynomial algorithms for partitioning a tree into single‐center subtrees to minimize flat service costs. Networks: An International Journal, 51(1), 78-89.
Becker, R., Lari, I., Lucertini, M., & Simeone, B. (1998). Max‐min partitioning of grid graphs into connected components. Networks: An International Journal, 32(2), 115-125.
Becker, R. I., Schach, S. R., & Perl, Y. (1982). A shifting algorithm for min-max tree partitioning. Journal of the ACM (JACM), 29(1), 58-67.
Benati, S., Puerto, J., & Rodriguez-Chia, A. M. (2017). Clustering data that are graph connected. European Journal of Operational Research, 261(1), 43-53.
Bruglieri, M., & Cordone, R. (2016). Partitioning a graph into minimum gap components. Electronic Notes in Discrete Mathematics, 55, 33-36.
Bruglieri, M., Cordone, R., & Caurio, V. (2017, June). A metaheuristic for the minimum gap graph partitioning problem. In Proceedings of the 15th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (pp. 23-26).
Bruglieri, M., & Cordone, R. (2021). Metaheuristics for the minimum gap graph partitioning problem. Computers & Operations Research, 132, 105301.
Bruglieri, M., Cordone, R., Lari, I., Ricca, F., & Scozzari, A. (2021). On finding connected balanced partitions of trees. Discrete Applied Mathematics, 299, 1-16.
Chlebíková, J. (1996). Approximating the maximally balanced connected partition problem in graphs. Information Processing Letters, 60(5), 225-230.
De Paola, F., Fontana, N., Galdiero, E., Giugni, M., degli Uberti, G. S., & Vitaletti, M. (2014). Optimal design of district metered areas in water distribution networks. Procedia Engineering, 70, 449-457.
De Simone, C., Lucertini, M., Pallottino, S., & Simeone, B. (1990). Fair dissections of spiders, worms, and caterpillars. Networks, 20(3), 323-344.
Dehghani, M., Trojovská, E., & Trojovský, P. (2022). A new human-based metaheuristic algorithm for solving optimization problems on the base of simulation of driving training process. Scientific reports, 12(1), 9924.
Engelbrecht, A. P. (2007). Computational intelligence: an introduction. John Wiley & Sons.
Erdos, P. & Renyi, A. (1959). On random graphs. Publ. Math 6(18), 290-297.
Goldschmidt, O., & Hochbaum, D. S. (1988, October). Polynomial algorithm for the k-cut problem. In [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science (pp. 444-451). IEEE Computer Society.
Gomes, R., Sousa, J., Muranho, J., & Marques, A. S. (2015). Different design criteria for district metered areas in water distribution networks. Procedia Engineering, 119, 1221-1230.
Hochbaum, D. S. (2019). Algorithms and complexity of range clustering. Networks, 73(2), 170-186.
Hubert, L. J. (1974). Some applications of graph theory to clustering. Psychometrika, 39(3), 283-309.
Ito, T., Nishizeki, T., Schröder, M., Uno, T., & Zhou, X. (2012). Partitioning a weighted tree into subtrees with weights in a given range. Algorithmica, 62, 823-841.
Kennedy, J., & Eberhart, R. (1995, November). Particle swarm optimization. In Proceedings of ICNN’95-international conference on neural networks (Vol. 4, pp. 1942-1948). ieee.
Khishe, M., & Mosavi, M. R. (2020). Chimp optimization algorithm. Expert systems with applications, 149, 113338.
Krauthgamer, R., Naor, J., & Schwartz, R. (2009, January). Partitioning graphs into balanced components. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms (pp. 942-949). Society for Industrial and Applied Mathematics.
Lari, I., Ricca, F., Puerto, J., & Scozzari, A. (2016). Partitioning a graph into connected components with fixed centers and optimizing cost‐based objective functions or equipartition criteria. Networks, 67(1), 69-81.
Li Xiao, L. X., Li HongPeng, L. H., Niu DongLing, N. D., Wang Yan, W. Y., & Liu Gang, L. G. (2015). Optimization of GNSS-controlled land leveling system and related experiments, 31(3), 48–55.
Lucertini, M., Perl, Y., & Simeone, B. (1993). Most uniform path partitioning and its use in image processing. Discrete Applied Mathematics, 42(2-3), 227-256.
Mehlhorn, K. & Wagner, U. (2000). Connected k-partition problems. Journal of Al- gorithms, 37(1), 1-28.
Mirjalili, S., Mirjalili, S. M., & Lewis, A. (2014). Grey wolf optimizer. Advances in engineering software, 69, 46-61.
Puerto, J., & Sainz-Pardo, J. L. (2023). Partitioning a graph constraining the weight of its cuts. Available at SSRN 4341526.
Tang, X., Soukhal, A., & T’kindt, V. (2014). Preprocessing for a map sectorization problem by means of mathematical programming. Annals of Operations Research, 222, 551-569.
Downloads
Published
Issue
Section
License
Copyright (c) 2024 Ehab Morsy, Riham Moharam
This work is licensed under a Creative Commons Attribution 4.0 International License.
