Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem

摘要

The minimum conductance graph partitioning problem (MC-GPP) is to partition the vertex set of a graph into two disjoint subsets while minimizing the ratio between the number of the edges crossing the two subsets and the smallest volume of the two subsets, the volume of a vertex set being the sum of degrees of its vertices. MC-GPP has a variety of relevant applications, and however, is known to be NP-hard. In this work, we present a novel metaheuristic algorithm called "stagnation-aware breakout tabu search" for approximating MC-GPP. The algorithm combines a dedicated tabu search procedure to discover high-quality solutions and a self-adaptive perturbation procedure to overcome hard-to-escape local optimum traps. We perform extensive evaluations of the algorithm on five datasets of 110 benchmark instances in the literature. The key components of the proposed algorithm are analyzed to illustrate their influences on the performance of the algorithm. (C) 2019 Elsevier Ltd. All rights reserved.