Coverage versus supply cost in facility location: physics of frustrated spin systems

Chi Ho Yeung*, K.Y. Michael Wong, Bo Li

*Corresponding author for this work

Research output: Contribution to journalArticle

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.

Original languageEnglish
Article number062805
Number of pages14
JournalPhysical Review E
Volume89
Issue number6
DOIs
Publication statusPublished - 10 Jun 2014

Fingerprint

Facility Location
Spin Systems
Coverage
Physics
costs
physics
Costs
transportation networks
communication networks
energy consumption
frustration
messages
outlets
simplification
approximation
Antiferromagnet
Disordered Systems
Frustration
Transportation Networks
continuums

Cite this

Yeung, Chi Ho ; Wong, K.Y. Michael ; Li, Bo. / Coverage versus supply cost in facility location : physics of frustrated spin systems. In: Physical Review E. 2014 ; Vol. 89, No. 6.
@article{4d5cc8a7d5704de894f052e58bc1d196,
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.",
author = "Yeung, {Chi Ho} and Wong, {K.Y. Michael} and Bo Li",
year = "2014",
month = "6",
day = "10",
doi = "10.1103/PhysRevE.89.062805",
language = "English",
volume = "89",
journal = "Physical Review E",
issn = "1539-3755",
publisher = "American Physical Society",
number = "6",

}

Coverage versus supply cost in facility location : physics of frustrated spin systems. / Yeung, Chi Ho; Wong, K.Y. Michael; Li, Bo.

In: Physical Review E, Vol. 89, No. 6, 062805, 10.06.2014.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Coverage versus supply cost in facility location

T2 - physics of frustrated spin systems

AU - Yeung, Chi Ho

AU - Wong, K.Y. Michael

AU - Li, Bo

PY - 2014/6/10

Y1 - 2014/6/10

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84902477908&partnerID=8YFLogxK

U2 - 10.1103/PhysRevE.89.062805

DO - 10.1103/PhysRevE.89.062805

M3 - Article

AN - SCOPUS:84902477908

VL - 89

JO - Physical Review E

JF - Physical Review E

SN - 1539-3755

IS - 6

M1 - 062805

ER -