Thumbnail

Monte Carlo Graph Coloring

Cazenave, Tristan; Negrevergne, Benjamin; Sikora, Florian (2020), Monte Carlo Graph Coloring, in Cazenave, Tristan; Teytaud, Olivier; Winands, Mark H. M., Monte Carlo Search, Springer, p. 100-115. 10.1007/978-3-030-89453-5_8

View/Open
Type
Communication / Conférence
Date
2020
Conference title
First Workshop, MCS 2020, Held in Conjunction with IJCAI 2020
Conference date
2021-01
Conference city
virtuel
Book title
Monte Carlo Search
Book author
Cazenave, Tristan; Teytaud, Olivier; Winands, Mark H. M.
Publisher
Springer
ISBN
978-3-030-89453-5
Pages
100-115
Publication identifier
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