Statistical physics, optimization and source coding |
| |
Authors: | Riccardo Zecchina |
| |
Institution: | (1) International Centre for Theoretical Physics, Strada Costiera 11, I-34100 Trieste, Italy |
| |
Abstract: | The combinatorial problem of satisfying a given set of constraints that depend on N discrete variables is a fundamental one in optimization and coding theory. Even for instances of randomly generated problems, the question “does there exist an assignment to the variables that satisfies all constraints?” may become extraordinarily difficult to solve in some range of parameters where a glass phase sets in. We shall provide a brief review of the recent advances in the statistical mechanics approach to these satisfiability problems and show how the analytic results have helped to design a new class of message-passing algorithms — the survey propagation (SP) algorithms — that can efficiently solve some combinatorial problems considered intractable. As an application, we discuss how the packing properties of clusters of solutions in randomly generated satisfiability problems can be exploited in the design of simple lossy data compression algorithms. |
| |
Keywords: | Disordered systems random combinatorial problems survey propagation |
本文献已被 SpringerLink 等数据库收录! |
|