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[I]-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 mu   1 such that it is NP-hard to approximate within a factor of c(mu n) the volume of the largest [mu n]-simplex contained in an n-dimensional polytope with O(n) vertices. (c) 2006 Elsevier B.V. All rights reserved.
inapproximability computational complexity computational geometry parameterized computation