The network source location problem: ground state energy, entropy and effects of freezing

DOI10.1007/S10955-014-1002-2zbMATH Open1298.82032arXiv1209.4134OpenAlexW2070863803MaRDI QIDQ744574FDOQ744574

Authors: Hai-Ping Huang, Jack Raymond, K. Y. Michael Wong 

Publication date: 25 September 2014

Published in: Journal of Statistical Physics (Search for Journal in Brave)

Abstract: Ground state entropy of the network source location problem is evaluated at both the replica symmetric level and one-step replica symmetry breaking level using the entropic cavity method. The regime that is a focus of this study, is closely related to the vertex cover problem with randomly quenched covered nodes. The resulting entropic message passing inspired decimation and reinforcement algorithms are used to identify the optimal location of sources in single instances of transportation networks. The conventional belief propagation without taking the entropic effect into account is also compared. We find that in the glassy phase the entropic message passing inspired decimation yields a lower ground state energy compared to the belief propagation without taking the entropic effect. Using the extremal optimization algorithm, we study the ground state energy and the fraction of frozen hubs, and extend the algorithm to collect statistics of the entropy. The theoretical results are compared with the extremal optimization results.

Full work available at URL: https://arxiv.org/abs/1209.4134

Recommendations

• Static and dynamic source locations in undirected networks
• Statistical physics and network optimization problems
• Free energy rates for a class of very noisy optimization problems
• Maximum entropy analysis of flow and reaction networks
• Statistical mechanics of the directed 2-distance minimal dominating set problem

zbMATH Keywords

entropytransportation networkscavity methodmessage-passing algorithmsdisordered systems (theory)

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Stochastic programming (90C15) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30) Transportation, logistics and supply chain management (90B06) Stochastic network models in operations research (90B15)

Cites Work

• Information, Physics, and Computation
• A multi-commodity, multi-plant, capacitated facility location problem: Formulation and efficient heuristic solution.
• Survey propagation: An algorithm for satisfiability
• The cavity method at zero temperature
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• Next nearest neighbour Ising models on random graphs
• Local field distributions in spin glasses

This page was built for publication: The network source location problem: ground state energy, entropy and effects of freezing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q744574)