Generating all vertices of a polyhedron is hard
From MaRDI portal
Publication:5920505
DOI10.1007/s00454-008-9050-5zbMath1147.05040OpenAlexW2058094600WikidataQ59560590 ScholiaQ59560590MaRDI QIDQ5920505
Konrad Borys, Khaled M. Elbassioni, Endre Boros, Vladimir A. Gurvich, Leonid G. Khachiyan
Publication date: 16 April 2008
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-008-9050-5
enumerationNP-hardnegative cyclesdirected edge weighted graphinfeasible subsystems of system of linear inequalities
Linear programming (90C05) Enumeration in graph theory (05C30) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Related Items
Weighted digraphs and tropical cones, Farkas Certificates and Minimal Witnesses for Probabilistic Reachability Constraints, On characterizing full dimensional weak facets in DEA with variable returns to scale technology, Computing convex hulls and counting integer points with \texttt{polymake}, On the approximation of unbounded convex sets by polyhedra, Revisited aspects of the local set in CHSH Bell scenario, Robust homecare service capacity planning, Enumerating minimal dominating sets in chordal bipartite graphs, Derivative-free optimization of a rapid-cycling synchrotron, A polynomial-time-delay and polynomial-space algorithm for enumeration problems in multi-criteria optimization, Gorenstein braid cones and crepant resolutions, Maximal admissible faces and asymptotic bounds for the normal surface solution space, Output-polynomial enumeration on graphs of bounded (local) linear MIM-width, The negative cycles polyhedron and hardness of checking some polyhedral properties, 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, Scientific contributions of Leo Khachiyan (a short overview), A new method for determining all maximal efficient faces in multiple objective linear programming, On the hardness of computing intersection, union and Minkowski sum of polytopes, Optimizing the double description method for normal surface enumeration, Self-duality of polytopes and its relations to vertex enumeration and graph isomorphism, Complexity and algorithms for computing Voronoi cells of lattices, Complexity of methods for approximating convex compact bodies by double description polytopes and complexity bounds for a hyperball, Static Contract Checking with Abstract Interpretation, Sum of Squares Certificates for Containment of $\mathcal{H}$-Polytopes in $\mathcal{V}$-Polytopes, A semidefinite programming approach for solving multiobjective linear programming, Efficient geometric operations on convex polyhedra, with an application to reachability analysis of hybrid systems, Enumerating Vertices of Covering Polyhedra with Totally Unimodular Constraint Matrices, A polyhedral model for enumeration and optimization over the set of circuits, Complexity of approximating the vertex centroid of a polyhedron, The regularized feasible directions method for nonconvex optimization, Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices, Exploiting Symmetries in Polyhedral Computations, Forbidden Vertices, Sampling and Statistical Physics via Symmetry
Uses Software
Cites Work
- Random generation of combinatorial structures from a uniform distribution
- On generating all maximal independent sets
- A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
- The densest hemisphere problem
- The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable
- Primal-dual methods for vertex and facet enumeration
- Incremental convex hull algorithms are not output sensitive
- An optimal convex hull algorithm in any fixed dimension
- Efficient enumeration of the vertices of polyhedra associated with network LP's
- Some results concerning post-infeasibility analysis
- How good are convex hull algorithms?
- On the maximum feasible subsystem problem, IISs and IIS-hypergraphs
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Reverse search for enumeration
- Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron.
- Maximum-Minimum Sätze über Graphen
- The Complexity of Vertex Enumeration Methods
- Finding the convex hull facet by facet
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- An Algorithm for Finding All Vertices of Convex Polyhedral Sets
- The Complexity of Enumeration and Reliability Problems
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- Identifying Minimally Infeasible Subsystems of Inequalities
- Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
- An algorithm for determining all extreme points of a convex polytope
- IIS-Hypergraphs
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- An Algorithm for Convex Polytopes
- The complexity of theorem-proving procedures
- An Algorithm for Determining Irrelevant Constraints and all Vertices in Systems of Linear Inequalities
- Integer Programming and Combinatorial Optimization
- A Theorem on Boolean Matrices
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
