title: Coverage versus supply cost in facility location: physics of frustrated spin systems.
abstract: A comprehensive coverage is crucial for communication, supply, and transportation networks, yet it is limited by the requirement of extensive infrastructure and heavy energy consumption. Here, we draw an analogy between spins in antiferromagnet and outlets in supply networks, and apply techniques from the studies of disordered systems to elucidate the effects of balancing the coverage and supply costs on the network behavior. A readily applicable, coverage optimization algorithm is derived. Simulation results show that magnetized and antiferromagnetic domains emerge and coexist to balance the need for coverage and energy saving. The scaling of parameters with system size agrees with the continuum approximation in two dimensions and the tree approximation in random graphs. Due to frustration caused by the competition between coverage and supply cost, a transition between easy and hard computation regimes is observed. We further suggest a local expansion approach to greatly simplify the message updates which shed light on simplifications in other problems.
authors.affiliation: The Nonlinearity and Complexity Research Group, Aston University, Birmingham B4 7ET, United Kingdom and Department of Physics, The Hong Kong University of Science and Technology, Hong Kong and Department of Science and Environmental Studies, The Hong Kong Institute of Education, Tai Po, Hong Kong.
authors.forename: Chi Ho
authors.initials: CH
authors.lastname: Yeung
authors.affiliation: Department of Physics, The Hong Kong University of Science and Technology, Hong Kong.
authors.forename: K Y Michael
authors.initials: KY
authors.lastname: Wong
authors.affiliation: Department of Physics, The Hong Kong University of Science and Technology, Hong Kong.
authors.forename: Bo
authors.initials: B
authors.lastname: Li
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D018803:Models, Economic; D015233:Models, Statistical