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
article (PDF)