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

A Study of Breakout Local Search for the Minimum Sum Coloring Problem

Abstract :

Given an undirected graph G = (V,E), the minimum sum coloring problem (MSCP) is to find a legal assignment of colors (represented by natural numbers) to each vertex of G such that the total sum of the colors assigned to the vertices is minimized. In this paper, we present Breakout Local Search (BLS) for MSCP which combines some essential features of several well-established metaheuristics. BLS explores the search space by a joint use of local search and adaptive perturbation strategies. Tested on 27 commonly used benchmark instances, our algorithm shows competitive performance with respect to recently proposed heuristics and is able to find new record-breaking results for 4 instances.

Type de document :
Communication dans un congrès
Liste complète des métadonnées
Contributeur : Okina Université d'Angers <>
Soumis le : mercredi 9 juin 2021 - 15:04:27
Dernière modification le : jeudi 10 juin 2021 - 03:39:57

Lien texte intégral




Una Benlic, Jin-Kao Hao. A Study of Breakout Local Search for the Minimum Sum Coloring Problem. 9th International Conference, SEAL 2012, 2012, Hanoï, Vietnam. pp.128 - 137, ⟨10.1007/978-3-642-34859-4_13⟩. ⟨hal-03255392⟩



Consultations de la notice