The Complexity of Vertex Enumeration Methods
From MaRDI portal
Publication:3313620
DOI10.1287/MOOR.8.3.381zbMath0531.90064OpenAlexW1991287453MaRDI QIDQ3313620
Publication date: 1983
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.8.3.381
computational complexityconvex polyhedronlinear inequalitiesvertex enumerationenumeration of all vertices
Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Linear inequalities of matrices (15A39) Polytopes and polyhedra (52Bxx)
Related Items (45)
A graphical study of comparative probabilities ⋮ Farkas Certificates and Minimal Witnesses for Probabilistic Reachability Constraints ⋮ Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces ⋮ A general algorithm for determining all essential solutions and inequalities for any convex polyhedron ⋮ On the complexity of some basic problems in computational convexity. I. Containment problems ⋮ Enumerative techniques for solving some nonconvex global optimization problems ⋮ How good are convex hull algorithms? ⋮ Segments in enumerating faces ⋮ Bounds on the complexity of halfspace intersections when the bounded faces have small dimension ⋮ Computing shadow prices with multiple Lagrange multipliers ⋮ Multi-criteria analysis with partial information about the weighting coefficients ⋮ A representation of an efficiency equivalent polyhedron for the objective set of a multiple objective linear program ⋮ The complexity of the \(K\)th largest subset problem and related problems ⋮ Eigenpolytope Universality and Graphical Designs ⋮ Maximal admissible faces and asymptotic bounds for the normal surface solution space ⋮ Unnamed Item ⋮ A tree traversal algorithm for decision problems in knot theory and 3-manifold topology ⋮ Which nonnegative matrices are slack matrices? ⋮ A Calculation of all Separating Hyperplanes of two Convex Polytopes ⋮ A basis enumeration algorithm for linear systems with geometric applications ⋮ On-line and off-line vertex enumeration by adjacency lists ⋮ The harmonic polytope ⋮ A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra ⋮ H ∞ PID controller design for Lur’e systems and its application to a ball and wheel apparatus ⋮ The vector linear program solver Bensolve -- notes on theoretical background ⋮ Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron. ⋮ On a calculation of an arbitrary separating hyperplane of convex polyhedral sets ⋮ Separating support hyperplanes for a pair of convex polyhedral sets ⋮ Optimizing the double description method for normal surface enumeration ⋮ A complete description of cones and polytopes including hypervolumes of all facets of a polytope ⋮ Incremental convex hull algorithms are not output sensitive ⋮ A method of transferring polyhedron between the intersection-form and the sum-form ⋮ Complexity and algorithms for computing Voronoi cells of lattices ⋮ Random walks on the vertices of transportation polytopes with constant number of sources ⋮ Interpreting linear systems of equalities and inequalities. Application to the water supply problem ⋮ Enumerating Vertices of Covering Polyhedra with Totally Unimodular Constraint Matrices ⋮ Generating all vertices of a polyhedron is hard ⋮ Computational complexity of norm-maximization ⋮ Complexity of approximating the vertex centroid of a polyhedron ⋮ Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices ⋮ A framework for the complexity of high-multiplicity scheduling problems ⋮ Sufficient optimality criterion for linearly constrained, separable concave minimization problems ⋮ Selected bibliography on degeneracy ⋮ Bounds on the number of vertices of perturbed polyhedra ⋮ Efficient enumeration of the vertices of polyhedra associated with network LP's
This page was built for publication: The Complexity of Vertex Enumeration Methods
