On the complexity of four polyhedral set containment problems
From MaRDI portal
Publication:3703587
DOI10.1007/BF01582241zbMath0581.90060OpenAlexW2116403087WikidataQ59592741 ScholiaQ59592741MaRDI QIDQ3703587
James B. Orlin, Robert M. Freund
Publication date: 1985
Published in: Mathematical Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01582241
Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Polytopes and polyhedra (52Bxx)
Related Items
Linear programs with an additional rank two reverse convex constraint, D.c sets, d.c. functions and nonlinear equations, Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces, Tight Approximations of Dynamic Risk Measures, On the complexity of some basic problems in computational convexity. I. Containment problems, Verification of Hybrid Systems, Finding Minimum Volume Circumscribing Ellipsoids Using Generalized Copositive Programming, Convex hulls, oracles, and homology, Some Recent Developments in Spectrahedral Computation, Segments in enumerating faces, SHARPENING GEOMETRIC INEQUALITIES USING COMPUTABLE SYMMETRY MEASURES, On a cone covering problem, Novel approaches to the discrimination problem, Outer-product-free sets for polynomial optimization and oracle-based cuts, Learning Topic Models: Identifiability and Finite-Sample Analysis, Which nonnegative matrices are slack matrices?, Sparse Probability Assessment Heuristic Based on Orthogonal Matching Pursuit, Spherical coverage verification, Colorful linear programming, Nash equilibrium, and pivots, Inner and outer approximations of polytopes using boxes., Mathematical programs with a two-dimensional reverse convex constraint, On the hardness of computing intersection, union and Minkowski sum of polytopes, Self-duality of polytopes and its relations to vertex enumeration and graph isomorphism, Is a finite intersection of balls covered by a finite union of balls in Euclidean spaces?, 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, On the implementation and strengthening of intersection cuts for QCQPs, Computational complexity of norm-maximization, A Semidefinite Hierarchy for Containment of Spectrahedra, On the complexity of approximating the maximal inscribed ellipsoid for a polytope
Cites Work
