Arrêt de service programmé du vendredi 10 juin 16h jusqu’au lundi 13 juin 9h. Pour en savoir plus
Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

Breakout Local Search for the Max-Cutproblem

Abstract :

Given an undirected graph G=(V,E)G=(V,E) where each edge of E is weighted with an integer number, the maximum cut problem (Max-Cut) is to partition the vertices of V into two disjoint subsets so as to maximize the total weight of the edges between the two subsets. As one of Karp's 21 NP-complete problems, Max-Cut has attracted considerable attention over the last decades. In this paper, we present Breakout Local Search (BLS) for Max-Cut. BLS explores the search space by a joint use of local search and adaptive perturbation strategies. The proposed algorithm shows excellent performance on the set of well-known maximum cut benchmark instances in terms of both solution quality and computational time. Out of the 71 benchmark instances, BLS is capable of finding new improved results in 34 cases and attaining the previous best-known result for 35 instances, within computing times ranging from less than 1 s to 5.6 h for the largest instance with 20,000 vertices.

Type de document :
Article dans une revue
Liste complète des métadonnées
Contributeur : Okina Univ Angers Connectez-vous pour contacter le contributeur
Soumis le : jeudi 10 juin 2021 - 10:28:12
Dernière modification le : mercredi 20 octobre 2021 - 03:19:08

Lien texte intégral




Una Benlic, Jin-Kao Hao. Breakout Local Search for the Max-Cutproblem. Engineering Applications of Artificial Intelligence, Elsevier, 2013, 26 (3), pp.1162-1173. ⟨10.1016/j.engappai.2012.09.001⟩. ⟨hal-03256209⟩



Consultations de la notice