|
Discrete Mathematics and Optimization Seminar
|
Oct. 6, 2008
Think locally, act globally: how to search with iterated maps
Simon Gravel
Cornell University
|
We show how simple dynamical systems can be designed to search efficiently
for solutions of difficult constraint problems such as Boolean
satisfaction, sphere packing, and the folding of proteins. In this
approach constraints are seen as geometrical objects, and the solutions
are encoded in attractive fixed points of the dynamical systems. We
compare the performance of the resulting general-purpose search strategy
to the state-of-the-art in Boolean satisfaction and packing problems, and
discuss some unexpected sphere arrangements found by this approach.
|
|
|
|