Research Article
Decimation Algorithm Based on Correlations for Constraint Satisfaction Problems on Random Networks
@INPROCEEDINGS{10.1109/WIOPT.2009.5291594, author={Saburo Higuchi}, title={Decimation Algorithm Based on Correlations for Constraint Satisfaction Problems on Random Networks}, proceedings={2nd International Workshop on Physics-Inspired Paradigms in Wireless Communications and Networks}, publisher={IEEE}, proceedings_a={PHYSCOMNET}, year={2009}, month={10}, keywords={constraint satisfaction problem belief propagation statistical mechanics factor graph correlation}, doi={10.1109/WIOPT.2009.5291594} }- Saburo Higuchi
Year: 2009
Decimation Algorithm Based on Correlations for Constraint Satisfaction Problems on Random Networks
PHYSCOMNET
IEEE
DOI: 10.1109/WIOPT.2009.5291594
Abstract
We propose a statistical physics inspired algorithm to solve locked occupation problems, which are hard discrete constraint satisfaction problems defined on random networks. The algorithm consists of finding correlation among variables and using that information for reducing the problem to a smaller one. Namely one replaces the problem at hand with the one with less variables and slightly smaller set of solutions until the problem becomes simple enough for analysis by enumeration. The result of numerical experiments suggests that it performs efficiently even when the set of solutions is disconnected for the random factor graphs with the truncated Poisson degree distribution.
Copyright © 2009–2025 IEEE
