Mesh permutation routing with locality

Abstract

Given the permutation routing problem on mesh-connected arrays with a known maximum distance, d, between any source- destination pair, we show how sorting and the greedy algorithm can be combined to yield a deterministic, asymptotically optimal algorithm for solving the problem. This simple algorithm runs in d+O(d/f(d)) time and requires an O(f;(d)) buffer size (or O(d) time and constant buffer size if we choose f(d) to be a constant). It also gives efficient solutions to the k-k routing problem with locality.