An Efficient Iterated Greedy Algorithm for the Maximum Bisection Problem

ABSTRACT

In this paper, we propose an iterated greedy algorithm, called IGLS (iterated greedy algorithm combined with local search), which enables the algorithm to explore a broader solution space, effectively escaping local optima and providing a more robust search mechanism. Additionally, local search strategies are integrated into our algorithm. This hybridisation of greedy and local search ensures that the algorithm benefits from the balanced search ability. We perform extensive experiments to evaluate the algorithm on diverse benchmark instances. The empirical evaluation demonstrates that the IGLS algorithm can produce high‐quality solutions and outperform the state‐of‐the‐art methods for handling large graphs.