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.
Categories: math.CO cs.DM