On random multi-dimensional assignment problems
On random multi-dimensional assignment problems
复制标题
关于随机多维分配问题
DOI：
10.1016/j.dam.2020.07.013
复制
发表时间：
2020
影响因子：
1.1
通讯作者：
Tkocz, Tomasz
中科院分区：
文献类型：
--
作者：
Frieze, Alan;Pegden, Wesley;Tkocz, Tomasz
我们研究了随机多维分配问题，其中费用分解为独立随机变量的和。特别地，在三维空间中，我们假设费用i，j，k满足i，j，k=ai，j+bi，k+cj，k，其中ai，j，bi，k，cj，k是独立的均匀[0，1]随机变量。我们的目标是最小化总成本，我们证明了一个简单的贪婪算法是一个(3+o(1))-近似。这与Wi、j、k是独立的指数率1随机变量的情况相反。在这里，由于Frieze和Sorkin，我们所知道的只是一个no(1)-近似。
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 uniform [0, 1] random variables. Our objective is to minimise the total cost and we show that whp 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.
登录
查看更多内容
寻找多指标轴向分配问题渐近最优计划的多项式算法
DOI：
--
发表时间：
2005
期刊：
影响因子：
--
作者：
V. M. Kravtsov
通讯作者：
V. M. Kravtsov
Parisi关于随机分配问题猜想的证明
影响因子：
2
作者：
Svante Linusson;Johan Wästlund
通讯作者：
Johan Wästlund
Parisi 和 Coppersmith-Sorkin 随机分配猜想的证明
影响因子：
1
作者：
Chandra Nair;B. Prabhakar;Mayank Sharma
通讯作者：
Mayank Sharma
三维轴向和平面随机分配问题的高效算法
DOI：
--
发表时间：
2010
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
A. Frieze;G. Sorkin
通讯作者：
G. Sorkin