Constraint optimization and landscapes

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We describe an effective landscape introduced in [1] for the analysis of Constraint Satisfaction problems, such as Sphere Packing, K-SAT and Graph Coloring. This geometric construction reexpresses these problems in the more familiar terms of optimization in rugged energy landscapes. In particular, it allows one to understand the puzzling fact that unsophisticated programs are successful well beyond what was considered to be the `hard' transition, and suggests an algorithm defining a new, higher, easy-hard frontier.
Contribution to STATPHYS23

Keywords

Quantum Physics, Statistical Mechanics, Computational Complexity, Adaptation and Self-Organizing Systems

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/169798

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0709.1023
 http://arxiv.org/abs/0709.1023
 Eur. Phys. J. B 64, 563-565 (2008)
 doi:10.1140/epjb/e2008-00052-x

Collections

arXiv