论文标题
最大重量凸层
Maximum Weight Convex Polytope
论文作者
论文摘要
我们研究了最大重量凸多物质问题，其中的目标是找到一个凸多物件，从而最大程度地提高了封闭点的总重量。在这项工作之前，此问题的唯一已知结果是$ O（n^3）$算法的$ 2 $尺寸，因为Bautista等人。我们表明，问题变成了$ \ Mathcal {np} $ - 难以在$ 3 $尺寸中完全解决，而$ \ Mathcal {np} $ - 对于任何$ n^{1/2-ε} $在$ 4 $或更多尺寸的$ n^{1/2-ε} $中很难近似。 ％\ polyapx complete $ 4 $尺寸，即使有二进制重量。我们还以$ 2 $尺寸的价格给出了一种新算法，尽管它具有与Bautsita等人的算法相同的$ O（n^3）$运行时间复杂性。
We study the maximum weight convex polytope problem, in which the goal is to find a convex polytope maximizing the total weight of enclosed points. Prior to this work, the only known result for this problem was an $O(n^3)$ algorithm for the case of $2$ dimensions due to Bautista et al. We show that the problem becomes $\mathcal{NP}$-hard to solve exactly in $3$ dimensions, and $\mathcal{NP}$-hard to approximate within $n^{1/2-ε}$ for any $ε> 0$ in $4$ or more dimensions. %\polyAPX-complete in $4$ dimensions even with binary weights. We also give a new algorithm for $2$ dimensions, albeit with the same $O(n^3)$ running time complexity as that of the algorithm of Bautsita et al.
