Generating all vertices of a polyhedron is hard
From MaRDI portal
(Redirected from Publication:5920505)
Generating all vertices of a polyhedron is hard (scientific article; zbMATH DE number 5264627)
Generating all vertices of a polyhedron is hard (scientific article; zbMATH DE number 5264627)
Consider a directed edge-weighted graph \(G\) where the arcs are weighted by real values. A cycle is negative if the sum of its edge weights is negative. The number of negative cycles may be exponential in the size of the input, i.e. the size of \(G\) and the weights. The main result says that enumerating all negative cycles is NP-hard, even if the edge weights consist of only two different values. The same result holds for the undirected case. As a consequence, enumerating all minimal infeasible subsystems of a system of linear inequalities is NP-hard. This is even true for linear systems involving at most two variables in each inequality. For generating maximal feasible subsystems the complexity is open. Enumerating all vertices of a rational polyhedron, given as the intersection of finitely many half-spaces, is NP-hard. For bounded polyhedra the complexity remains open.
Recommendations
Cites work
- A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
- A Theorem on Boolean Matrices
- An Algorithm for Convex Polytopes
- An algorithm for determining all extreme points of a convex polytope
- An Algorithm for Determining Irrelevant Constraints and all Vertices in Systems of Linear Inequalities
- An Algorithm for Finding All Vertices of Convex Polyhedral Sets
- An optimal convex hull algorithm in any fixed dimension
- Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron.
- Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Efficient enumeration of the vertices of polyhedra associated with network LP's
- Finding the convex hull facet by facet
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- How good are convex hull algorithms?
- scientific article; zbMATH DE number 2186837 (Why is no real title available?)
- scientific article; zbMATH DE number 3644821 (Why is no real title available?)
- scientific article; zbMATH DE number 3854804 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 3078984 (Why is no real title available?)
- scientific article; zbMATH DE number 3080072 (Why is no real title available?)
- Identifying Minimally Infeasible Subsystems of Inequalities
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- IIS-Hypergraphs
- Incremental convex hull algorithms are not output sensitive
- Integer Programming and Combinatorial Optimization
- Maximum-Minimum Sätze über Graphen
- On generating all maximal independent sets
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- On the maximum feasible subsystem problem, IISs and IIS-hypergraphs
- Primal-dual methods for vertex and facet enumeration
- Random generation of combinatorial structures from a uniform distribution
- Reverse search for enumeration
- Some results concerning post-infeasibility analysis
- The Complexity of Enumeration and Reliability Problems
- The complexity of theorem-proving procedures
- The Complexity of Vertex Enumeration Methods
- The densest hemisphere problem
- The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable
Cited in
(41)- Self-duality of polytopes and its relations to vertex enumeration and graph isomorphism
- A polyhedral model for enumeration and optimization over the set of circuits
- The regularized feasible directions method for nonconvex optimization
- Complexity of methods for approximating convex compact bodies by double description polytopes and complexity bounds for a hyperball
- Computing convex hulls and counting integer points with \texttt{polymake}
- Maximal admissible faces and asymptotic bounds for the normal surface solution space
- On the approximation of unbounded convex sets by polyhedra
- Weighted digraphs and tropical cones
- Sum of squares certificates for containment of \(\mathcal{H}\)-polytopes in \(\mathcal{V}\)-polytopes
- Exploiting symmetries in polyhedral computations
- Complexity and algorithms for computing Voronoi cells of lattices
- Static contract checking with abstract interpretation
- On characterizing full dimensional weak facets in DEA with variable returns to scale technology
- Optimizing the double description method for normal surface enumeration
- Generating all vertices of a polyhedron is hard
- scientific article; zbMATH DE number 5548206 (Why is no real title available?)
- Computational tools for solving a marginal problem with applications in Bell non-locality and causal modeling
- An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
- Sampling and Statistical Physics via Symmetry
- Farkas certificates and minimal witnesses for probabilistic reachability constraints
- Enumerating vertices of 0/1-polyhedra associated with 0/1-totally unimodular matrices
- A new method for determining all maximal efficient faces in multiple objective linear programming
- Enumerating vertices of covering polyhedra with totally unimodular constraint matrices
- Forbidden vertices
- Revisited aspects of the local set in CHSH Bell scenario
- Robust homecare service capacity planning
- Derivative-free optimization of a rapid-cycling synchrotron
- Gorenstein braid cones and crepant resolutions
- A polynomial-time-delay and polynomial-space algorithm for enumeration problems in multi-criteria optimization
- The negative cycles polyhedron and hardness of checking some polyhedral properties
- Deep learning the efficient frontier of convex vector optimization problems
- Lineup polytopes of products of simplices
- On certain polytopes associated to products of algebraic integer conjugates
- Maximum inscribed and minimum enclosing tropical balls of tropical polytopes and applications to volume estimation and uniform sampling
- Methods for identifying all extreme points of convex hulls in spaces of dimension greater than 3 revisited
- A semidefinite programming approach for solving multiobjective linear programming
- Efficient geometric operations on convex polyhedra, with an application to reachability analysis of hybrid systems
- Complexity of approximating the vertex centroid of a polyhedron
- Enumerating minimal dominating sets in chordal bipartite graphs
- Scientific contributions of Leo Khachiyan (a short overview)
- On the hardness of computing intersection, union and Minkowski sum of polytopes
This page was built for publication: Generating all vertices of a polyhedron is hard
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5920505)
