Emergence of algorithmically hard phases in transportation networks

K. Y. Michael Wong; Chi Ho Yeung

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

Research Article

Emergence of algorithmically hard phases in transportation networks

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.1109/WIOPT.2009.5291593,
    author={K. Y. Michael Wong and Chi Ho Yeung},
    title={Emergence of algorithmically hard phases in transportation networks},
    proceedings={2nd International Workshop on Physics-Inspired Paradigms in  Wireless Communications and Networks},
    publisher={IEEE},
    proceedings_a={PHYSCOMNET},
    year={2009},
    month={10},
    keywords={transportation networks; Resource management; Transportation},
    doi={10.1109/WIOPT.2009.5291593}
}

K. Y. Michael Wong
Chi Ho Yeung
Year: 2009
Emergence of algorithmically hard phases in transportation networks
PHYSCOMNET
IEEE
DOI: 10.1109/WIOPT.2009.5291593

K. Y. Michael Wong¹^,*, Chi Ho Yeung¹^,*

1: Dept. of Phys., Hong Kong Univ. of Sci. & Technol., Hong Kong, China

*Contact email: phkywong@ust.hk, phbill@ust.hk

Abstract

We study a model of transportation networks with nonlinear elements which represent local shortage of resources. Frustration arises from competition among the nodes to become satisfied. When the initial resources are uniform, algorithmically hard regimes emerge when the average availability of resources increases. These regimes are characterized by discrete fractions of satisfied nodes, resembling the Devil's staircase. Behavior similar to those in the vertex cover or close packing problems are found. When initial resources are bimodally distributed, such algorithmically hard regimes also emerge when the fraction of rich nodes increases.

Keywords: transportation networks; Resource management; Transportation

Published: 2009-10-23
Publisher: IEEE

: http://dx.doi.org/10.1109/WIOPT.2009.5291593