Polynomial-time approximation of largest simplices in \(V\)-polytopes.

DOI10.1016/S0166-218X(03)00226-9zbMath1165.68524MaRDI QIDQ1421471

Asa Packer

Publication date: 26 January 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

Computational complexityApproximation algorithmSimplexInapproximabilityDeterminant\(\mathbb{NP}\)-hardnessContainment problemsCrosspolytopePolynomial-time

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

Parameterized complexity and improved inapproximability for computing the largest \(j\)-simplex in a \(V\)-polytope, Exponential inapproximability of selecting a maximum volume sub-matrix, Unnamed Item, Sum of Squares Certificates for Containment of $\mathcal{H}$-Polytopes in $\mathcal{V}$-Polytopes, Approximation of convex sets by polytopes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On principal angles between subspaces in \(\mathbb{R}^n\)
• Parallelotopes of maximum volume in a simplex
• On the complexity of some basic problems in computational convexity. I. Containment problems
• Approximating quadratic programming with bound and quadratic constraints
• Oracle-polynomial-time approximation of largest simplices in convex bodies
• \(\mathbb N\mathbb P\)-hardness of largest contained and smallest containing simplices for \(V\)- and \(H\)-polytopes
• Largest \(j\)-simplices in \(n\)-polytopes
• Largest \(j\)-simplices in \(d\)-cubes: Some relatives of the Hadamard maximum determinant problem
• Largest parallelotopes contained in simplices
• Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces
• Matrix Analysis
• Finding the smallest triangles containing a given convex polygon
• An optimal algorithm for finding minimal enclosing triangles
• A PARALLEL ALGORITHM FOR ENCLOSED AND ENCLOSING TRIANGLES
• Introduction to the theory of complexity and approximation algorithms
• The Resolution of a Compositional Data Set into Mixtures of Fixed Source Compositions