Parameterized complexity and improved inapproximability for computing the largest j-simplex in a V-polytope |
| |
Authors: | Ioannis Koutis |
| |
Affiliation: | Computer Science Department, Carnegie Mellon University, Pittsburgh, PA 15213, USA |
| |
Abstract: | 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. |
| |
Keywords: | Computational complexity Computational geometry Inapproximability Parameterized computation |
本文献已被 ScienceDirect 等数据库收录! |
|