Deterministic and randomized polynomial-time approximation of radii
Deterministic and randomized polynomial-time approximation of radii
复制标题
DOI：
10.1112/s0025579300014364
复制
发表时间：
2001
期刊：
影响因子：
0.8
通讯作者：
A. Brieden;P. Gritzmann;R. Kannan;V. Klee;L. Lovász;M. Simonovits
中科院分区：
文献类型：
--
作者：
A. Brieden;P. Gritzmann;R. Kannan;V. Klee;L. Lovász;M. Simonovits
本文研究了n维lp空间中的凸体，其中每个凸体只能通过弱分离或优化预言机到达。研究了当n → ∞时，多项式时间逼近算法对物体K的直径、宽度、外切半径和内半径的渐近相对精度，以及在l ~ 2的情况下对K上范数的最大值的渐近相对精度。（欧几里德n-空间），Barany和Furedi在1987年的一个结果严重地限制了用任何确定性的方法来近似K的体积所能保证的相对精确度。多项式时间算法。这导致了一个类似的严重限制的相对精度的确定性多项式时间算法计算K的直径。然而，这些限制的准确性确定性计算很快就其次是戴尔，弗里兹和Kannan的工作表明，体积近似，任意好的精度可以达到与援助的适当随机化。因此，人们自然想知道直径是否也是如此。本文的第一个主要结果是，与体积的情况相反，随机化无助于近似直径。当允许随机化时，适用于确定性多项式时间计算的相同精度限制仍然适用。这个结论也适用于物体的宽度、外切半径和内半径，以及K上范数的最大化。第二个主要结果是，对于刚刚提到的五个半径测量中的每一个，当1≤p≤2时，确定性多项式时间近似的不可逼近性结果对于宽度和内径是最优的，当2≤p≤∞时，对于直径，外接圆半径和范数最大化是最优的，并且在其余情况下，在对数因子内是最优的。特别地，当p = 2时，所有都是最优的。通过产生确定性多项式时间近似算法建立最优性，该算法的准确度由准确度上界的正常数倍（独立于维度n）限定。由于该机构被假定为一个弱的预言，我们的方法属于算法理论的凸体发起的Grotschel，Lovasz和Schrijver。在确定性的情况下，我们锐化和扩展L 2的结果，由于这些作者，反在随机的情况下，我们完善了一些想法，早先提出的Lovasz和Simonovits。建立精度下限的算法使用l p单位球的某些多面体近似，
This paper is concerned with convex bodies in n-dimensional l p spaces, where each body is accessible only by a weak separation or optimization oracle. It studies the asymptotic relative accuracy, as n → ∞, of polynomial-time approximation algorithms for the diameter, width, circumradius, and inradius of a body K, and also for the maximum of the norm over K In the case of l 2 (Euclidean n-space), a 1987 result of Barany and Furedi severely limits the degree of relative accuracy that can be guaranteed in approximating K's volume by any deterministic polynomial-time algorithm. This led to a similarly severe limit on the relative accuracy of deterministic polynomial-time algorithms for computing K's diameter. However, these limitations on the accuracy of deterministic computation were soon followed by the work of Dyer, Frieze and Kannan showing that, for volume approximation, arbitrarily good accuracy can be attained with the aid of suitable randomization. It was therefore natural to wonder whether the same is true of the diameter. The first main result of this paper is that, in contrast to the situation for the volume, randomization does not help in approximating the diameter. The same limitation on accuracy that applies to deterministic polynomial-time computation still applies when randomization is permitted. This conclusion applies also to the width, circumradius, and inradius of a body, and to maximization of the norm over K. The second main result is that, for each of the five radius measurements just mentioned, the inapproximability results for deterministic polynomial-time approximation are optimal for width and inradius when 1≤p≤2, are optimal for diameter, circumradius, and norm-maximization when 2≤p≤∞, and in the remaining cases are within a logarithmic factor of being optimal. In particular, all are optimal when p = 2. The optimality is established by producing deterministic polynomial-time approximation algorithms whose accuracy is bounded below by a positive constant multiple (independent of the dimension n) of the upper bounds on accuracy. Since the bodies are assumed to be presented by a weak oracle, our approach belongs to the algorithmic theory of convex bodies initiated by Grotschel, Lovasz and Schrijver. In the deterministic case we sharpen and extend l 2 results due to these authors, anti in the randomized case we refine some ideas presented earlier by Lovasz and Simonovits. The algorithms that establish lower bounds on accuracy use certain polytopal approximations of l p unit balls that