Algorithms for Polytope Covering and Approximation
Algorithms for Polytope Covering and Approximation
复制标题
多面体覆盖和逼近算法
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
K. Clarkson
中科院分区：
文献类型：
--
作者：
K. Clarkson
本文给出了一个多面体覆盖的算法：设L和U是RD中的点集，共包含n个点。来自U的L的覆盖是C⊂U的集合，L是C的凸包的子集。设c是这样一个最小覆盖的大小，如果它存在的话。这里给出的随机化算法找到了一个大小不超过c(5dlnc)的覆盖，其中c足够大。该算法的预期时间为O(c2n1+δ)。更准确地说，时间界限是
$$O(CN^{1+增量}+c(NC)^{1/(1+伽马/(1+增量))})$$
，其中γγ1/[d/2]。以前的最优界是在O(N)时间内的co(Logn)覆盖大小。[MS92b]将一种变形算法应用于用更简单的多面体的边界来逼近多面体的边界的问题。对于适当的度量，具有误差e的逼近需要c=O(d/e)d−1个顶点，并且该算法给出了具有c(5d3 ln(1/e))个顶点的逼近。这些算法应用了以前用于小维线性规划的思想。
This paper gives an algorithm for polytope covering: let L and U be sets of points in Rd, comprising n points altogether. A cover for L from U is a set C⊂U with L a subset of the convex hull of C. Suppose c is the size of a smallest such cover, if it exists. The randomized algorithm given here finds a cover of size no more than c(5dln c), for c large enough. The algorithm requires O(c2n1+δ) expected time. More exactly, the time bound is
$$O(cn^{1 + delta } + c(nc)^{1/(1 + gamma /(1 + delta ))} )$$
, where γγ1/[d/2]. The previous best bounds were cO(log n) cover size in O(nd) time.[MS92b] A variant algorithm is applied to the problem of approximating the boundary of a polytope with the boundary of a simpler polytope. For an appropriate measure, an approximation with error e requires c=O(d/e)d−1 vertices, and the algorithm gives an approximation with c(5d3 ln(1/e)) vertices. The algorithms apply ideas previously used for small-dimensional linear programming.