On the complexity of some basic problems in computational convexity. I. Containment problems
From MaRDI portal
Publication:1344616
Recommendations
Cites work
- A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
- A combinatorial bound for linear programming and related problems
- A complete description of the traveling salesman polytope on 8 nodes
- A geometric inequality and the complexity of computing volume
- A new polynomial-time algorithm for linear programming
- A PARALLEL ALGORITHM FOR ENCLOSED AND ENCLOSING TRIANGLES
- A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
- A proof that there exists a circumscribing cube around any bounded closed convex set in \(\mathbb{R}^3\)
- A quasi-polynomial bound for the diameter\\of graphs of polyhedra
- A Variable-Complexity Norm Maximization Problem
- An optimal algorithm for finding minimal enclosing triangles
- Applications of random sampling in computational geometry. II
- Approximation schemes for covering and packing problems in image processing and VLSI
- Average-Case Stability of Gaussian Elimination
- Computational complexity of norm-maximization
- Computing the volume is difficult
- Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization
- D-optimum weighing designs
- Deciding uniqueness in norm maximazation
- Determinants Whose Elements Are 0 and 1
- Determinants with Elements ± 1
- Diameter, width, closest line pair, and parametric searching
- Error Analysis of Direct Methods of Matrix Inversion
- Estimates for the minimal width of polytopes inscribed in convex bodies
- Faces with large diameter on the symmetric traveling salesman polytope
- Finding the convex hull facet by facet
- Finding the smallest triangles containing a given convex polygon
- Geometric algorithms and combinatorial optimization
- Good and Bad Radii of Convex Polygons
- Growth in Gaussian Elimination
- Hadamard Matrices and Some Generalisations
- Hadamard matrices and their applications
- Hadamard matrices and their applications
- Hard Enumeration Problems in Geometry and Combinatorics
- scientific article; zbMATH DE number 3644821 (Why is no real title available?)
- scientific article; zbMATH DE number 431987 (Why is no real title available?)
- scientific article; zbMATH DE number 446693 (Why is no real title available?)
- scientific article; zbMATH DE number 3145759 (Why is no real title available?)
- scientific article; zbMATH DE number 3858224 (Why is no real title available?)
- scientific article; zbMATH DE number 3872174 (Why is no real title available?)
- scientific article; zbMATH DE number 3876377 (Why is no real title available?)
- scientific article; zbMATH DE number 3877692 (Why is no real title available?)
- scientific article; zbMATH DE number 4200003 (Why is no real title available?)
- scientific article; zbMATH DE number 4201996 (Why is no real title available?)
- scientific article; zbMATH DE number 3898613 (Why is no real title available?)
- scientific article; zbMATH DE number 3904331 (Why is no real title available?)
- scientific article; zbMATH DE number 3943559 (Why is no real title available?)
- scientific article; zbMATH DE number 3943560 (Why is no real title available?)
- scientific article; zbMATH DE number 3965243 (Why is no real title available?)
- scientific article; zbMATH DE number 3980484 (Why is no real title available?)
- scientific article; zbMATH DE number 4032498 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 3177183 (Why is no real title available?)
- scientific article; zbMATH DE number 37080 (Why is no real title available?)
- scientific article; zbMATH DE number 43279 (Why is no real title available?)
- scientific article; zbMATH DE number 50254 (Why is no real title available?)
- scientific article; zbMATH DE number 124523 (Why is no real title available?)
- scientific article; zbMATH DE number 194093 (Why is no real title available?)
- scientific article; zbMATH DE number 3466805 (Why is no real title available?)
- scientific article; zbMATH DE number 3521387 (Why is no real title available?)
- scientific article; zbMATH DE number 3522990 (Why is no real title available?)
- scientific article; zbMATH DE number 3558962 (Why is no real title available?)
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 4123531 (Why is no real title available?)
- scientific article; zbMATH DE number 480239 (Why is no real title available?)
- scientific article; zbMATH DE number 480243 (Why is no real title available?)
- scientific article; zbMATH DE number 480249 (Why is no real title available?)
- scientific article; zbMATH DE number 665697 (Why is no real title available?)
- scientific article; zbMATH DE number 1142309 (Why is no real title available?)
- scientific article; zbMATH DE number 194636 (Why is no real title available?)
- scientific article; zbMATH DE number 3804333 (Why is no real title available?)
- scientific article; zbMATH DE number 863487 (Why is no real title available?)
- scientific article; zbMATH DE number 863498 (Why is no real title available?)
- scientific article; zbMATH DE number 236540 (Why is no real title available?)
- scientific article; zbMATH DE number 3249560 (Why is no real title available?)
- scientific article; zbMATH DE number 3261280 (Why is no real title available?)
- scientific article; zbMATH DE number 3314644 (Why is no real title available?)
- scientific article; zbMATH DE number 3345859 (Why is no real title available?)
- scientific article; zbMATH DE number 3352656 (Why is no real title available?)
- scientific article; zbMATH DE number 3052220 (Why is no real title available?)
- scientific article; zbMATH DE number 3060028 (Why is no real title available?)
- scientific article; zbMATH DE number 3069632 (Why is no real title available?)
- scientific article; zbMATH DE number 3102063 (Why is no real title available?)
- Hyperrhombs inscribed to convex bodies
- Increasing Paths on the One-Skeleton of a Convex Body and the Directions of Line Segments on the Boundary of a Convex Body
- Large Growth Factors in Gaussian Elimination with Pivoting
- Largest \(j\)-simplices in \(n\)-polytopes
- Linear Programming in Linear Time When the Dimension Is Fixed
- Linear-Time Algorithms for Linear Programming in R^3 and Related Problems
- Minimal ellipsoids and their duals
- Multisurface method of pattern separation for medical diagnosis applied to breast cytology.
- Note on the computational complexity of \(j\)-radii of polytopes in \(\mathbb R^ n\)
- Odd Minimum Cut-Sets and b-Matchings
- On Growth in Gaussian Elimination with Complete Pivoting
- On Hotelling's Weighing Problem
- On Maximal Regular Polyhedra Inscribed in a Regular Polyhedron
- On Minimum Volume Ellipsoids Containing Part of a Given Ellipsoid
- On recognizing integer polyhedra
- On the complexity of approximating the maximal inscribed ellipsoid for a polytope
- On the complexity of computing the diameter of a polytope
- On the Complexity of Computing the Volume of a Polyhedron
- On the complexity of four polyhedral set containment problems
- On the Complexity of Some Common Geometric Location Problems
- On the complexity of some geometric problems in unbounded dimension
- On theorems of Borsuk-Ulam, Kakutani-Yamabe-Yujobô and Dyson. II
- Optimal packing and covering in the plane are NP-complete
- Paths on Polytopes
- Paths, Trees, and Flowers
- Pivot size in Gaussian elimination
- Polygonal approximation by the minimax method
- Polygons Circumscribed About Closed Convex Curves
- Polytope Containment and Determination by Linear Probes
- Probabilistic analysis of optimization algorithms - some aspects from a practical point of view
- Some Improvements in Weighing and Other Experimental Techniques
- The d-Step Conjecture and Its Relatives
- The adjacency relation on the traveling salesman polytope is NP-Complete
- The complexity of elementary algebra and geometry
- The complexity of satisfiability problems
- The complexity of theorem-proving procedures
- The Complexity of Vertex Enumeration Methods
- The coordinex problem and its relation to the conjecture of Wilkinson
- The Hadamard Maximum Determinant Problem
- The maximum numbers of faces of a convex polytope
- The only convex body with extremal distance from the ball is the simplex
- The travelling salesman problem and a class of polyhedra of diameter two
- Unsolved problems in geometry
- Über das Löwnersche Ellipsoid und sein Analogon unter den einem Eikörper einbeschriebenen Ellipsoiden
Cited in
(40)- 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.
- Geometric clustering in normed planes
- Elementary geometry on the integer lattice
- Some clustering algorithms in normed planes
- 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
- The adaptive convexification algorithm for semi-infinite programming with arbitrary index sets
- No dimension-independent core-sets for containment under homothetics
- On the co-NP-completeness of the zonotope containment problem
- How to solve a semi-infinite optimization problem
- Sum of squares certificates for containment of \(\mathcal{H}\)-polytopes in \(\mathcal{V}\)-polytopes
- Polytopic discrete-time models for systems with time-varying delays
- On the complexity of four polyhedral set containment problems
- (Deterministic) algorithms that compute the volume of polytopes
- Deterministic and randomized polynomial‐time approximation of radii
- Some recent developments in spectrahedral computation
- Maximum Volume Inscribed Ellipsoid: A New Simplex-Structured Matrix Factorization Framework via Facet Enumeration and Convex Optimization
- Polytope Containment and Determination by Linear Probes
- A collision detection approach for maximizing the material utilization
- A matrix Positivstellensatz with lifting polynomials
- Computing maximal copies of polyhedra contained in a polyhedron
- A semidefinite hierarchy for containment of spectrahedra
- Minimal containment under homothetics: a simple cutting plane approach
- Deciding robust feasibility and infeasibility using a set containment approach: an application to stationary passive gas network operations
- New Algorithms for k-Center and Extensions
- Embedding of a homothete in a convex compactum: an algorithm and its convergence
- On clustering bodies: geometry and polyhedral approximation
- Recent advances in nonconvex semi-infinite programming: applications and algorithms
- Diversities and the generalized circumradius
- On feasible sets for MPC and their approximations
- Efficient subspace approximation algorithms
- The best ways to slice a polytope
- The computational complexity of the weak gravity conjecture
- On the reverse Loomis-Whitney inequality
- Fast subspace approximation via greedy least-squares
- New algorithms for \(k\)-center and extensions
- Generalized semi-infinite programming: a tutorial
This page was built for publication: On the complexity of some basic problems in computational convexity. I. Containment problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1344616)
