2nd International Workshop on Physics-Inspired Paradigms in Wireless Communications and Networks

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
Saburo Higuchi1,*
  • 1: Department of Applied Mathematics and Informatics Ryukoku University Otsu, Shiga, 520-2194, Japan
*Contact email: hig@math.ryukoku.ac.jp

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.