The Complexity of Vertex Enumeration Methods

DOI10.1287/MOOR.8.3.381zbMATH Open0531.90064OpenAlexW1991287453MaRDI QIDQ3313620FDOQ3313620

Authors: Martin Dyer 

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

Recommendations

• How good are convex hull algorithms?
• The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable
• On-line and off-line vertex enumeration by adjacency lists
• scientific article
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra

zbMATH Keywords

computational complexitylinear inequalitiesconvex polyhedronvertex enumerationenumeration of all vertices

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Polytopes and polyhedra (52Bxx) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Linear inequalities of matrices (15A39)

Cited In (62)

• Double description method revisited
• Some applications of combinatorial optimization in parallel computing
• Traversing combinatorial 0/1-polytopes via optimization
• Eigenpolytope Universality and Graphical Designs
• A complete description of cones and polytopes including hypervolumes of all facets of a polytope
• A graphical study of comparative probabilities
• A framework for the complexity of high-multiplicity scheduling problems
• Enumerating Vertices of Covering Polyhedra with Totally Unimodular Constraint Matrices
• Title not available (Why is that?)
• Hard Enumeration Problems in Geometry and Combinatorics
• The complexity of the \(K\)th largest subset problem and related problems
• Farkas Certificates and Minimal Witnesses for Probabilistic Reachability Constraints
• Error control in polytope computations
• Estimating the number of vertices of a polyhedron
• Beneath-and-Beyond revisited
• Optimizing the double description method for normal surface enumeration
• Title not available (Why is that?)
• The use of edge-directions and linear programming to enumerate vertices
• Computing shadow prices with multiple Lagrange multipliers
• Generating all vertices of a polyhedron is hard
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• The harmonic polytope
• Bounds on the number of vertices of perturbed polyhedra
• A basis enumeration algorithm for linear systems with geometric applications
• Which nonnegative matrices are slack matrices?
• A Calculation of all Separating Hyperplanes of two Convex Polytopes
• A representation of an efficiency equivalent polyhedron for the objective set of a multiple objective linear program
• H _∞ PID controller design for Lur’e systems and its application to a ball and wheel apparatus
• Title not available (Why is that?)
• On-line and off-line vertex enumeration by adjacency lists
• Computational complexity of norm-maximization
• Sufficient optimality criterion for linearly constrained, separable concave minimization problems
• Multi-criteria analysis with partial information about the weighting coefficients
• Title not available (Why is that?)
• Interpreting linear systems of equalities and inequalities. Application to the water supply problem
• Separating support hyperplanes for a pair of convex polyhedral sets
• Complexity of approximating the vertex centroid of a polyhedron
• Title not available (Why is that?)
• Computational experience with the reverse search vertex enumeration algorithm
• Selected bibliography on degeneracy
• The complexity of the vertex-minor problem
• A method of transferring polyhedron between the intersection-form and the sum-form
• Complexity and algorithms for computing Voronoi cells of lattices
• A general algorithm for determining all essential solutions and inequalities for any convex polyhedron
• Segments in enumerating faces
• A tree traversal algorithm for decision problems in knot theory and 3-manifold topology
• Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces
• The shrinking-and-expanding method for the graph enumeration
• Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices
• Maximal admissible faces and asymptotic bounds for the normal surface solution space
• Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron.
• Efficient enumeration of the vertices of polyhedra associated with network LP's
• On the complexity of some basic problems in computational convexity. I. Containment problems
• How good are convex hull algorithms?
• Bounds on the complexity of halfspace intersections when the bounded faces have small dimension
• Title not available (Why is that?)
• The vector linear program solver Bensolve -- notes on theoretical background
• Enumerative techniques for solving some nonconvex global optimization problems
• On a calculation of an arbitrary separating hyperplane of convex polyhedral sets
• Title not available (Why is that?)
• Random walks on the vertices of transportation polytopes with constant number of sources
• Incremental convex hull algorithms are not output sensitive

This page was built for publication: The Complexity of Vertex Enumeration Methods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3313620)