  We study random multidimensional assignment problems where the costs
decompose into the sum of independent random variables. In particular, in three
dimensions, we assume that the costs $W_{i,j,k}$ satisfy
$W_{i,j,k}=a_{i,j}+b_{i,k}+c_{j,k}$ where the $a_{i,j},b_{i,k},c_{j,k}$ are
independent exponential rate 1 random variables. Our objective is to minimize
the total cost and we show that w.h.p. a simple greedy algorithm is a
$(3+o(1))$-approximation. This is in contrast to the case where the $W_{i,j,k}$
are independent exponential rate 1 random variables. Here all that is known is
an $n^{o(1)}$-approximation, due to Frieze and Sorkin.
