Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
A Multilevel Tabu Search with Backtracking for Exploring Weak Schur Numbers
verfasst von : Denis Robilliard, Cyril Fonlupt, Virginie Marion-Poty, Amine Boumaza
Erschienen in: Artificial Evolution
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
. Although studied since 1941, only the weak Schur numbers
WS
(1) through
WS
(4) are precisely known, for
k
≥ 5 the
WS
(
k
) are only bracketed within rather loose bounds. We tackle this problem with a tabu search scheme, enhanced by a multilevel and backtracking mechanism. While heuristic approaches cannot definitely settle the value of weak Schur numbers, they can improve the lower bounds by finding suitable partitions, which in turn can provide ideas on the structure of the problem. In particular we exhibit a suitable 6-partition of [1,574] obtained by tabu search, improving on the current best lower bound for
WS
(6).