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

https://hal.univ-angers.fr/hal-03256209
Contributeur : Okina Université d'Angers <>
Soumis le : jeudi 10 juin 2021 - 10:28:12
Dernière modification le : vendredi 11 juin 2021 - 03:29:58

Lien texte intégral

Identifiants

Collections

Citation

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⟩

Partager

Métriques

Consultations de la notice

16