Item

Abstract

We consider the permutation routing problem on two-dimensional
n x n meshes. To be practical, a routing algorithm is required
to ensure very small queue sizes Q, and very low running time T,
not only asymptotically but particularly also for the practically
important n up to 1000. With a technique inspired by a
scheme of Kaklamanis/Krizanc/Rao, we obtain a near-optimal
result: T = 2 n + O(1) with Q = 2. Although Q is very
attractive now, the lower order terms in T make this algorithm
highly impractical. Therefore we present simple schemes which are
asymptotically slower, but have T around 3 n for all n and Q
between 2 and 8.