On the co-NP-completeness of the zonotope containment problem

DOI10.1016/J.EJCON.2021.06.028zbMath1478.90147OpenAlexW3176457131MaRDI QIDQ2068561

Adrian Kulmburg, Matthias Althoff

Publication date: 19 January 2022

Published in: European Journal of Control (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejcon.2021.06.028

zbMATH Keywords

optimizationcomputational complexityzonotopecomputational geometrycontainment problemzonotope norm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Estimation and detection in stochastic control theory (93E10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Attainable sets, reachability (93B03)

Uses Software

• CORA

Cites Work

• Voronoi polytopes for polyhedral norms on lattices
• Computational complexity of norm-maximization
• Guaranteed state estimation by zonotopes
• Robust MPC of constrained discrete-time nonlinear systems based on approximated reachable sets
• Computing reachable sets of hybrid systems using a combination of zonotopes and polytopes
• Minimax linear programming problem
• On the complexity of some basic problems in computational convexity. I. Containment problems
• Finding optimal shadows of polytopes
• Complexity and approximation of finding the longest vector sum
• Containment Problems for Polytopes and Spectrahedra
• Reachset Conformance Testing of Hybrid Automata
• Robust fault estimation based on zonotopic Kalman filter for discrete‐time descriptor systems
• Computing the Continuous Discretely
• A radial basis function method for global optimization

This page was built for publication: On the co-NP-completeness of the zonotope containment problem