Survey Propagation methods

Efficient optimization and state selection in random Satisfiability problems

Autor*innen

• Demian Battaglia

Parameter

• 156 Seiten
• 6 Lesestunden

• Naturwissenschaften
• Physik
• Weltraum & Astronomie

Mehr zum Buch

Focusing on the optimization of random Constraint Satisfaction Problems (CSPs), the book explores the challenges posed by numerous competing conditions in various applications, from Sudokus to digital design. It introduces the Survey Propagation algorithm, which effectively tackles difficult instances through probabilistic message exchanges in factor graphs, outperforming traditional methods. The text also examines the typical-case complexity of random K-Satisfiability Problems and discusses innovative uses of Survey Propagation in lossy data compression, transforming complexity into a computational advantage.

• Sprache: Englisch
• Erscheinungsdatum: 2010
• Einband: Paperback