Efficient algorithms for three‐dimensional axial and planar random assignment problems
Efficient algorithms for three‐dimensional axial and planar random assignment problems
复制标题
三维轴向和平面随机分配问题的高效算法
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
G. Sorkin
中科院分区：
文献类型：
--
作者：
A. Frieze;G. Sorkin
对于随机二维分配问题的期望成本，已知有漂亮的公式，但在更高的维度上，甚至连缩放都不知道。在三维及以上的空间中，这个问题有自然的“轴向”和“平面”版本，两者都是NP-困难的。对于大小为n的三维轴向随机分配实例，成本为Ω（1/ n），本文的主要结果是一个线性时间算法，该算法以高概率找到成本O（n-1+o（1））的解决方案。对于三维平面分配，下界为Ω（n），我们给出了一个新的高效的基于匹配的算法，该算法以高概率返回成本为O（n log n）的解。© 2013 Wiley Periodicals，Inc.随机结构算法，46，160-196，2015
Beautiful formulas are known for the expected cost of random two‐dimensional assignment problems, but in higher dimensions even the scaling is not known. In three dimensions and above, the problem has natural “Axial” and “Planar” versions, both of which are NP‐hard. For 3‐dimensional Axial random assignment instances of size n, the cost scales as Ω(1/ n), and a main result of the present paper is a linear‐time algorithm that, with high probability, finds a solution of cost O(n–1+o(1)). For 3‐dimensional Planar assignment, the lower bound is Ω(n), and we give a new efficient matching‐based algorithm that with high probability returns a solution with cost O(n log n). © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 160–196, 2015