Resource relocation on asymmetric networks

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.