Thumbnail

Monte Carlo Graph Coloring

Cazenave, Tristan; Negrevergne, Benjamin; Sikora, Florian (2020), Monte Carlo Graph Coloring, IJCAI Workshop, 2021-01, Yokohama (virtual), Japan

Voir/Ouvrir
Type
Communication / Conférence
Date
2020
Titre du colloque
IJCAI Workshop
Date du colloque
2021-01
Ville du colloque
Yokohama (virtual)
Pays du colloque
Japan
Métadonnées
Afficher la notice complète
Auteur(s)
Cazenave, Tristan
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Negrevergne, Benjamin
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Sikora, Florian cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Résumé (EN)
Graph Coloring is probably one of the most studied and famous problem in graph algorithms. Exact methods fail to solve instances with more than few hundred vertices, therefore, a large number of heuristics have been proposed. Nested Monte Carlo Search (NMCS) and Nested Rollout Policy Adaptation (NRPA) are Monte Carlo search algorithms for single player games. Surprisingly, few work has been dedicated to evaluating Monte Carlo search algorithms to combinatorial graph problems. In this paper we expose how to efficiently apply Monte Carlo search to Graph Coloring and compare this approach to existing ones.
Mots-clés
Monte Carlo