Can I read On Random Multi-dimensional Assignment Problems on EtoBox?

On Random Multi-dimensional Assignment Problems by Frieze, Alan; Pegden, Wesley; Tkocz, Tomasz is a scholarly article available to read on EtoBox.

What is On Random Multi-dimensional Assignment Problems about?

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.

Author

Frieze, Alan; Pegden, Wesley; Tkocz, Tomasz

Published

2019

Language

EN