An Improved Driving Training-Based Optimization Algorithm for the Minimum Gap Graph Connected Partition Problem

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.