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

https://hal.univ-angers.fr/hal-03255392
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

Identifiants

Collections

Citation

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⟩

Partager

Métriques

Consultations de la notice

14