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.