On the complexity of some basic problems in computational convexity. I. Containment problems
From MaRDI portal
Publication:1344616
DOI10.1016/0012-365X(94)00111-UzbMath0824.68052MaRDI QIDQ1344616
Publication date: 6 November 1995
Published in: Discrete Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Computational aspects related to convexity (52B55) Linear programming (90C05) Boolean programming (90C09)
Related Items
The Blaschke-Steinhardt point of a planar convex set, Geometric clustering in normed planes, Largest \(j\)-simplices in \(n\)-polytopes, New algorithms for \(k\)-center and extensions, Some Recent Developments in Spectrahedral Computation, Polytopic Discrete-Time Models for Systems with Time-Varying Delays, Elementary geometry on the integer lattice, On clustering bodies: geometry and polyhedral approximation, The adaptive convexification algorithm for semi-infinite programming with arbitrary index sets, Recent advances in nonconvex semi-infinite programming: applications and algorithms, Diversities and the generalized circumradius, No dimension-independent core-sets for containment under homothetics, On feasible sets for MPC and their approximations, Deciding Robust Feasibility and Infeasibility Using a Set Containment Approach: An Application to Stationary Passive Gas Network Operations, Polynomial-time approximation of largest simplices in \(V\)-polytopes., Inner and outer approximations of polytopes using boxes., Generalized semi-infinite programming: a tutorial, (Deterministic) algorithms that compute the volume of polytopes, Efficient subspace approximation algorithms, A collision detection approach for maximizing the material utilization, How to solve a semi-infinite optimization problem, Minimal containment under homothetics: a simple cutting plane approach, On the reverse Loomis-Whitney inequality, Maximum Volume Inscribed Ellipsoid: A New Simplex-Structured Matrix Factorization Framework via Facet Enumeration and Convex Optimization, Some clustering algorithms in normed planes, Deterministic and randomized polynomial‐time approximation of radii, Sum of Squares Certificates for Containment of $\mathcal{H}$-Polytopes in $\mathcal{V}$-Polytopes, A Matrix Positivstellensatz with Lifting Polynomials, Fast subspace approximation via greedy least-squares, On the co-NP-completeness of the zonotope containment problem, Computing Maximal Copies of Polyhedra Contained in a Polyhedron, New Algorithms for k-Center and Extensions, A Semidefinite Hierarchy for Containment of Spectrahedra, On computing the diameter of a point set in high dimensional Euclidean space., Symmetric conference matrices and locally largest regular crosspolytopes in cubes
Cites Work
- 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
- 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
