Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00202
Resource relocation on asymmetric networks
D. Jacob Wildstrom
Vol. 14, no. 2, pp. 149-163, 2010. Regular paper.
Abstract The necessary information to optimally serve sequential requests at
the vertices of an undirected, unweighted graph with a single mobile
resource is a known result of Chung, Graham, and Saks; however,
generalizations of this concept to directed and weighted graphs
present unforeseen and surprising changes in the necessary lookahead
for strategic optimization. A pair of edges of unequal weights and
opposite orientation can serve to simulate a communication or
transportation connection with asymmetric costs, as may arise in a
transportation network from prevailing winds or elevation changes,
or in a communication network from aDSL or a similar technology.
This research explores the complications introduced by asymmetric
connections within even very small networks. We consider the dynamic
relocation problem on a two-vertex system and find that, even in
this simplest possible asymmetric graph, the necessary lookahead for
optimal relocation may be arbitrarily large. This investigation also
gives rise to a linear-time algorithm to determine the optimizing
real-time response to any request sequence which uniquely determines
an optimal response.
|
Submitted: January 2009.
Reviewed: November 2009.
Revised: November 2009.
Accepted: November 2009.
Final: November 2009.
Published: January 2010.
Communicated by
Gerhard J. Woeginger
|
Journal Supporters
|