Polynomial-time approximation of largest simplices in V-polytopes
This paper considers the problem of computing the squared volume of a largest j-dimensional simplex in an arbitrary d-dimensional polytope P given by its vertices (a V-polytope), for arbitrary integers j and d with 1?j?d. The problem was shown by Gritzmann, Klee and Larman to be -hard. This paper examines the possible accuracy of deterministic polynomial-time approximation algorithms for the problem. On the negative side, it is shown that unless , no such algorithm can approximately solve the problem within a factor of less than 1.09. It is also shown that the -hardness and inapproximability continue to hold when the polytope P is restricted to be an affine crosspolytope. On the positive side, a simple deterministic polynomial-time approximation algorithm for the problem is described. The algorithm takes as input integers j and d with 1?j?d and a V-polytope P of dimension d. It returns a j-simplex S?P such that
90c30 68q17 68w25 52b55