On random multi-dimensional assignment problems

01/22/2019

∙

by   Alan Frieze, et al.

∙

0

∙

share

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.