TY - JOUR

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

AU - Koutis, Ioannis

N1 - Funding Information:
✩ This work was supported in part by the National Science Foundation under grants CCR-9902091, ACI-0086093, and CCR-0122581. E-mail address: ioannis.koutis@cs.cmu.edu (I. Koutis).
Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.

PY - 2006/10/16

Y1 - 2006/10/16

N2 - 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.

AB - 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.

KW - Computational complexity

KW - Computational geometry

KW - Inapproximability

KW - Parameterized computation

UR - http://www.scopus.com/inward/record.url?scp=33745662129&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33745662129&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2006.05.006

DO - 10.1016/j.ipl.2006.05.006

M3 - Article

AN - SCOPUS:33745662129

VL - 100

SP - 8

EP - 13

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 1

ER -