Largest j-simplices in n-polytopes

DOI10.1007/BF02574058zbMATH Open0826.52014OpenAlexW2000646287MaRDI QIDQ1892425FDOQ1892425

D. G. Larman, Peter Gritzmann, Victor Klee

Publication date: 2 July 1995

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131376

Recommendations

• Polynomial-time approximation of largest simplices in \(V\)-polytopes.
• Parameterized complexity and improved inapproximability for computing the largest \(j\)-simplex in a \(V\)-polytope
• \(\mathbb N\mathbb P\)-hardness of largest contained and smallest containing simplices for \(V\)- and \(H\)-polytopes
• Maximal \(j\)-simplices in the real \(d\)-dimensional unit cube
• On largest volume simplices and sub-determinants

zbMATH Keywords

computational complexitypolytopesinscribed simpliceslargest simplices

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) (n)-dimensional polytopes (52B11) Computational aspects related to convexity (52B55) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)

Cites Work

• A new polynomial-time algorithm for linear programming
• Title not available (Why is that?)
• Reducibility among Combinatorial Problems
• Geometric algorithms and combinatorial optimization
• Applications of random sampling in computational geometry. II
• Polynomial algorithms in linear programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of satisfiability problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• The maximum numbers of faces of a convex polytope
• Title not available (Why is that?)
• On The Complexity of Computing Mixed Volumes
• Some new results on smoothness and rotundity in normed linear spaces
• An optimal algorithm for finding minimal enclosing triangles
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• Finding the smallest triangles containing a given convex polygon
• On recognizing integer polyhedra
• Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces
• Hard Enumeration Problems in Geometry and Combinatorics
• Title not available (Why is that?)
• On the complexity of some basic problems in computational convexity. I. Containment problems
• Title not available (Why is that?)
• Computational complexity of norm-maximization
• Diameter, width, closest line pair, and parametric searching
• Deciding uniqueness in norm maximazation
• Largest \(j\)-simplices in \(d\)-cubes: Some relatives of the Hadamard maximum determinant problem
• On maximal simplices inscribed in a central convex set
• Die meisten konvexen Körper sind glatt, aber nicht zu glatt
• A PARALLEL ALGORITHM FOR ENCLOSED AND ENCLOSING TRIANGLES
• Title not available (Why is that?)
• Title not available (Why is that?)
• A random polynomial time algorithm for well-routing convex bodies
• The content of some extreme simplexes

Cited In (19)

• Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering
• Parameterized complexity and improved inapproximability for computing the largest \(j\)-simplex in a \(V\)-polytope
• Title not available (Why is that?)
• \(\mathbb N\mathbb P\)-hardness of largest contained and smallest containing simplices for \(V\)- and \(H\)-polytopes
• SISAL Revisited
• What is known about unit cubes
• \(n\)-cubes inscribed in simplices
• Polynomial-time approximation of largest simplices in \(V\)-polytopes.
• Sum of squares certificates for containment of \(\mathcal{H}\)-polytopes in \(\mathcal{V}\)-polytopes
• Largest \(j\)-simplices in \(d\)-cubes: Some relatives of the Hadamard maximum determinant problem
• Approximation of convex sets by polytopes
• Title not available (Why is that?)
• On largest volume simplices and sub-determinants
• Largest parallelotopes contained in simplices
• On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices
• Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration
• On the complexity of some basic problems in computational convexity. I. Containment problems
• On the parameterized intractability of determinant maximization
• Exponential inapproximability of selecting a maximum volume sub-matrix

This page was built for publication: Largest \(j\)-simplices in \(n\)-polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1892425)