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

Ioannis Koutis

doi:10.1016/j.ipl.2006.05.006

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

Ioannis Koutis

Research output: Contribution to journal › Article › peer-review

15 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 language	English (US)
Pages (from-to)	8-13
Number of pages	6
Journal	Information Processing Letters
Volume	100
Issue number	1
DOIs	https://doi.org/10.1016/j.ipl.2006.05.006
State	Published - Oct 16 2006
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Keywords

Computational complexity
Computational geometry
Inapproximability
Parameterized computation

Access to Document

10.1016/j.ipl.2006.05.006

Cite this

@article{83db71741b15481cb252ab51e87c268f,

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

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",

author = "Ioannis Koutis",

note = "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: [email protected] (I. Koutis).",

year = "2006",

month = oct,

day = "16",

doi = "10.1016/j.ipl.2006.05.006",

language = "English (US)",

volume = "100",

pages = "8--13",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "1",

}

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: [email protected] (I. Koutis).

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

SN - 0020-0190

VL - 100

SP - 8

EP - 13

JO - Information Processing Letters

JF - Information Processing Letters

IS - 1

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this