The constrained migration problem arises in the memory management of large multiprocessor
systems. Given a network of processors, each of which has its own local memory, the purpose
of this problem is to find an efficient migration strategy which locates each writable page at an
appropriate processor by migration to reduce the total access cost, while considering the actual
capacity of each local memory. Although this problem is focused recently in the competitive
analysis area for on-line algorithms, only a few results are known so far about this problem. This
paper examines the on-line constrained migration problem deeper by attacking some special case of
the problem which we named the direct-mapped constrained migration problem, where all processors
are assumed to manage pages in their local memory using the same hash function.
For the direct-mapped constrained migration problem we present an optimal 3-competitive deter-
ministic on-line algorithm when the network consists of only 2 nodes. Furthermore we develop two
O(1)-competitive on-line algorithms for uniform graphs which are either deterministic or mem-
oryless. Interestingly this competitive ratio breaks the previous best upper bound obtained by
applying known algorithms for the constrained migration problem to this problem. Observing this
fact, we also give an important conjecture on the constrained m