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
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, 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
