Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

A Memetic Approach for the Max-Cut Problem

Abstract :

The max-cut problem is to partition the vertices of a weighted graph G = (V,E) into two subsets such that the weight sum of the edges crossing the two subsets is maximized. This paper presents a memetic max-cut algorithm (MACUT) that relies on a dedicated multi-parent crossover operator and a perturbation-based tabu search procedure. Experiments on 30 G-set benchmark instances show that MACUT competes favorably with 6 state-of-the-art max-cut algorithms, and for 10 instances improves on the best known results ever reported in the literature.

Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal.univ-angers.fr/hal-03255565
Contributeur : Okina Université d'Angers Connectez-vous pour contacter le contributeur
Soumis le : mercredi 9 juin 2021 - 16:08:12
Dernière modification le : jeudi 10 juin 2021 - 03:39:57

Lien texte intégral

Identifiants

Collections

Citation

Qinghua Wu, Jin-Kao Hao. A Memetic Approach for the Max-Cut Problem. 12th International Conference, PPSN 12, 2012, Taormine, Italy. pp.297 - 306, ⟨10.1007/978-3-642-32964-7_30⟩. ⟨hal-03255565⟩

Partager

Métriques

Consultations de la notice

13