Parameterized complexity and improved inapproximability for computing the largest j-simplex in a V-polytope

We consider the problem of computing the squared volume of the largest j-simplex contained in an n-dimensional polytope presented by its vertices (a V-polytope). We show that the related decision problem is W[1]-complete, with respect to the parameter j. We also improve the constant inapproximability factor given in [A. Packer, Polynomial-time approximation of largest simplices in V-polytopes, Discrete Appl. Math. 134 (1-3) (2004) 213-237], by showing that there are constants μ<1,c>1 such that it is NP-hard to approximate within a factor of cμn the volume of the largest ⌊μn⌋-simplex contained in an n-dimensional polytope with O(n) vertices.