Polynomial-time approximation of largest simplices in V-polytopes Original Research Article

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 NP-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 P=NP, no such algorithm can approximately solve the problem within a factor of less than 1.09. It is also shown that the NP-hardness and inapproximability continue to hold when the polytope P is restricted to be an affine crosspolytope.