  The data arrangement problem on regular trees (DAPT) consists in assigning
the vertices of a given graph G to the leaves of a d-regular tree T such that
the sum of the pairwise distances of all pairs of leaves in T which correspond
to edges of G is minimised. Luczak and Noble [6] have shown that this problem
is NP-hard for every fixed d larger than or equal to 2. In this paper we
propose construction and local search heuristics for the DAPT and introduce a
lower bound for this problem. The analysis of the performance of the heuristics
is based on two considerations: a) the quality of the solutions produced by the
heuristics as compared to the respective lower bounds b) for a special class of
instances with known optimal solution we evaluate the gap between the optimal
value of the objective function and the objective function value attained by
the heuristic solution, respectively.
