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

DOI10.1007/S10955-014-1002-2MaRDI QIDQ744574zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

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)