No, Coreset, No Cry
No, Coreset, No Cry
复制标题
不，Coreset，不哭
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Sariel Har
中科院分区：
文献类型：
--
作者：
Sariel Har
我们表明，对于 R 3 中的 2-slabs 问题，核心集不存在，从而证明有效解决该问题的自然方法是不可行的。从积极的一面来看，对于 R 3 中的点集 P，我们描述了一种近线性时间算法，用于计算 P 的最小宽度 2-slab 覆盖的 (1 + e) 近似。这是为用 k-slab 覆盖点集的问题提供有效的近似算法的第一步。
We show that coresets do not exist for the problem of 2-slabs in R 3 , thus demonstrating that the natural approach for solving approximately this problem efficiently is infeasible. On the positive side, for a point set P in R 3 , we describe a near linear time algorithm for computing a (1 + e)-approximation to the minimum width 2-slab cover of P. This is a first step in providing an efficient approximation algorithm for the problem of covering a point set with k-slabs.