Thumbnail

Monte Carlo Graph Coloring

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

View/Open
Type
Communication / Conférence
Date
2020
Conference title
IJCAI Workshop
Conference date
2021-01
Conference city
Yokohama (virtual)
Conference country
Japan
Metadata
Show full item record
Author(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]
Abstract (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.
Subjects / Keywords
Monte Carlo