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

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)8-13
Number of pages6
JournalInformation Processing Letters
Volume100
Issue number1
DOIs
StatePublished - Oct 16 2006
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Keywords

  • Computational complexity
  • Computational geometry
  • Inapproximability
  • Parameterized computation

Fingerprint Dive into the research topics of 'Parameterized complexity and improved inapproximability for computing the largest j-simplex in a V-polytope'. Together they form a unique fingerprint.

Cite this