Investigating Monte-Carlo Methods on the Weak Schur Problem

Abstract : Nested Monte-Carlo Search (NMC) and Nested Rollout Policy Adaptation (NRPA) are Monte-Carlo tree search algorithms that have proved their efficiency at solving one-player game problems, such as morpion solitaire or sudoku 16x16, showing that these heuristics could potentially be applied to constraint problems. In the field of Ramsey theory, the weak Schur number WS(k) is the largest integer n for which their exists a partition into k subsets of the integers [1, n] such that there is no x < y < z all in the same subset with x + y = z. Several studies have tackled the search for better lower bounds for the Weak Schur numbers WS(k), k ≥ 4. In this paper we investigate this problem using NMC and NRPA, and obtain a new lower bound for WS(6), namely WS(6) ≥ 582.
Type de document :
Communication dans un congrès
EvoCop, Apr 2013, Vienne, Austria. pp.191 - 201, 2013, 〈10.1007/978-3-642-37198-1_17〉
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01406479
Contributeur : Fabien Teytaud <>
Soumis le : jeudi 1 décembre 2016 - 11:24:53
Dernière modification le : vendredi 2 décembre 2016 - 01:05:12
Document(s) archivé(s) le : mercredi 22 mars 2017 - 23:54:25

Fichier

evo13.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Shalom Eliahou, Cyril Fonlupt, Jean Fromentin, Virginie Marion-Poty, Denis Robilliard, et al.. Investigating Monte-Carlo Methods on the Weak Schur Problem. EvoCop, Apr 2013, Vienne, Austria. pp.191 - 201, 2013, 〈10.1007/978-3-642-37198-1_17〉. 〈hal-01406479〉

Partager

Métriques

Consultations de la notice

68

Téléchargements de fichiers

43