On largest volume simplices and sub-determinants
On largest volume simplices and sub-determinants
复制标题
关于最大体积单纯形和次行列式
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Carsten Moldenhauer
中科院分区：
文献类型：
--
作者：
M. D. Summa;F. Eisenbrand;Yuri Faenza;Carsten Moldenhauer
我们表明，在QD中找到最大体积的单纯形，可以在多项式时间内使用O（log d）d/2的因子（log d）d/2近似。 d（d -1）/2的khachiyan。
另一方面，我们证明存在常数c> 1，因此，即使n = o（d），除非我们的硬度结果，否存在一种依赖于最近采样技术的CD及其算法，其中C再次是常数。
我们表明，对于找到D×N矩阵的亚测定因素的最大绝对值的问题，相似的结果存在。
We show that the problem of finding the simplex of largest volume in the convex hull of n points in Qd can be approximated with a factor of O(log d)d/2 in polynomial time. This improves upon the previously best known approximation guarantee of d(d−1)/2 by Khachiyan.
On the other hand, we show that there exists a constant c > 1 such that this problem cannot be approximated with a factor of cd, unless P = NP. Our hardness result holds even if n = O(d), in which case there exists a cd-approximation algorithm that relies on recent sampling techniques, where c is again a constant.
We show that similar results hold for the problem of finding the largest absolute value of a subdeterminant of a d × n matrix.