On the complexity of some basic problems in computational convexity. I. Containment problems

DOI10.1016/0012-365X(94)00111-UzbMath0824.68052MaRDI QIDQ1344616

Peter Gritzmann, Victor Klee

Publication date: 6 November 1995

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

zbMATH Keywords

linear programming; sensitivity analysis; computational convexity; pseudoboolean programming

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

52B05: Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)

52B55: Computational aspects related to convexity

90C05: Linear programming

90C09: Boolean programming

Related Items

(Deterministic) algorithms that compute the volume of polytopes, Deterministic and randomized polynomial‐time approximation of radii, New Algorithms for k-Center and Extensions, New algorithms for \(k\)-center and extensions, Generalized semi-infinite programming: a tutorial, The Blaschke-Steinhardt point of a planar convex set, Polynomial-time approximation of largest simplices in \(V\)-polytopes., Inner and outer approximations of polytopes using boxes., On computing the diameter of a point set in high dimensional Euclidean space., Symmetric conference matrices and locally largest regular crosspolytopes in cubes, Largest \(j\)-simplices in \(n\)-polytopes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A combinatorial bound for linear programming and related problems
• On Growth in Gaussian Elimination with Complete Pivoting
• Paths, Trees, and Flowers
• Hadamard Matrices and Some Generalisations
• The complexity of satisfiability problems
• Determinants with Elements ± 1
• Paths on Polytopes
• The maximum numbers of faces of a convex polytope
• Increasing Paths on the One-Skeleton of a Convex Body and the Directions of Line Segments on the Boundary of a Convex Body
• The Hadamard Maximum Determinant Problem
• The complexity of theorem-proving procedures
• Polygons Circumscribed About Closed Convex Curves
• Determinants Whose Elements Are 0 and 1
• Some Improvements in Weighing and Other Experimental Techniques
• On Hotelling's Weighing Problem
• Hadamard matrices and their applications
• Hadamard matrices and their applications
• Estimates for the minimal width of polytopes inscribed in convex bodies
• Diameter, width, closest line pair, and parametric searching
• Deciding uniqueness in norm maximazation
• Computational complexity of norm-maximization
• Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization
• A new polynomial-time algorithm for linear programming
• On theorems of Borsuk-Ulam, Kakutani-Yamabe-Yujobô and Dyson. II
• Über das Löwnersche Ellipsoid und sein Analogon unter den einem Eikörper einbeschriebenen Ellipsoiden
• The coordinex problem and its relation to the conjecture of Wilkinson
• A geometric inequality and the complexity of computing volume
• Computing the volume is difficult
• The complexity of elementary algebra and geometry
• Probabilistic analysis of optimization algorithms - some aspects from a practical point of view
• Minimal ellipsoids and their duals
• D-optimum weighing designs
• Optimal packing and covering in the plane are NP-complete
• A complete description of the traveling salesman polytope on 8 nodes
• Unsolved problems in geometry
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• Faces with large diameter on the symmetric traveling salesman polytope
• Geometric algorithms and combinatorial optimization
• Hyperrhombs inscribed to convex bodies
• On the complexity of approximating the maximal inscribed ellipsoid for a polytope
• On the complexity of computing the diameter of a polytope
• The only convex body with extremal distance from the ball is the simplex
• Applications of random sampling in computational geometry. II
• Largest \(j\)-simplices in \(n\)-polytopes
• Note on the computational complexity of \(j\)-radii of polytopes in \(\mathbb R^ n\)
• Pivot size in Gaussian elimination
• On the complexity of some geometric problems in unbounded dimension
• On recognizing integer polyhedra
• A proof that there exists a circumscribing cube around any bounded closed convex set in \(\mathbb{R}^3\)
• The Complexity of Vertex Enumeration Methods
• Polygonal approximation by the minimax method
• On the Complexity of Some Common Geometric Location Problems
• Good and Bad Radii of Convex Polygons
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Average-Case Stability of Gaussian Elimination
• Multisurface method of pattern separation for medical diagnosis applied to breast cytology.
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Finding the convex hull facet by facet
• Finding the smallest triangles containing a given convex polygon
• On the complexity of four polyhedral set containment problems
• A Variable-Complexity Norm Maximization Problem
• Hard Enumeration Problems in Geometry and Combinatorics
• An optimal algorithm for finding minimal enclosing triangles
• The d-Step Conjecture and Its Relatives
• Approximation schemes for covering and packing problems in image processing and VLSI
• Linear Programming in Linear Time When the Dimension Is Fixed
• Growth in Gaussian Elimination
• On the Complexity of Computing the Volume of a Polyhedron
• Error Analysis of Direct Methods of Matrix Inversion
• On Maximal Regular Polyhedra Inscribed in a Regular Polyhedron
• Odd Minimum Cut-Sets and b-Matchings
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• A PARALLEL ALGORITHM FOR ENCLOSED AND ENCLOSING TRIANGLES
• The travelling salesman problem and a class of polyhedra of diameter two
• The adjacency relation on the traveling salesman polytope is NP-Complete
• Large Growth Factors in Gaussian Elimination with Pivoting
• On Minimum Volume Ellipsoids Containing Part of a Given Ellipsoid
• Polytope Containment and Determination by Linear Probes