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

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)

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; zbMATH DE number 5548206
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra

Cited in

(66)

• Double description method revisited
• A complete description of cones and polytopes including hypervolumes of all facets of a polytope
• Traversing combinatorial 0/1-polytopes via optimization
• Eigenpolytope Universality and Graphical Designs
• Some applications of combinatorial optimization in parallel computing
• H _∞ PID controller design for Lur’e systems and its application to a ball and wheel apparatus
• A basis enumeration algorithm for linear systems with geometric applications
• Hard Enumeration Problems in Geometry and Combinatorics
• scientific article; zbMATH DE number 482137 (Why is no real title available?)
• The complexity of the vertex-minor problem
• Bounds on the complexity of halfspace intersections when the bounded faces have small dimension
• Separating support hyperplanes for a pair of convex polyhedral sets
• A representation of an efficiency equivalent polyhedron for the objective set of a multiple objective linear program
• Computational experience with the reverse search vertex enumeration algorithm
• 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
• The use of edge-directions and linear programming to enumerate vertices
• A method of transferring polyhedron between the intersection-form and the sum-form
• Segments in enumerating faces
• Interpreting linear systems of equalities and inequalities. Application to the water supply problem
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• scientific article; zbMATH DE number 1393410 (Why is no real title available?)
• Complexity of approximating the vertex centroid of a polyhedron
• scientific article; zbMATH DE number 1961535 (Why is no real title available?)
• A graphical study of comparative probabilities
• The complexity of the \(K\)th largest subset problem and related problems
• Computing shadow prices with multiple Lagrange multipliers
• On-line and off-line vertex enumeration by adjacency lists
• The vector linear program solver \textit{Bensolve} -- notes on theoretical background
• Random walks on the vertices of transportation polytopes with constant number of sources
• Selected bibliography on degeneracy
• An iterative vertex enumeration method for objective space based vector optimization algorithms
• Which nonnegative matrices are slack matrices?
• A Calculation of all Separating Hyperplanes of two Convex Polytopes
• Generating all vertices of a polyhedron is hard
• Estimating the number of vertices of a polyhedron
• Efficient enumeration of the vertices of polyhedra associated with network LP's
• Incremental convex hull algorithms are not output sensitive
• Enumerative techniques for solving some nonconvex global optimization problems
• Maximal admissible faces and asymptotic bounds for the normal surface solution space
• Computational complexity of norm-maximization
• Multi-criteria analysis with partial information about the weighting coefficients
• The shrinking-and-expanding method for the graph enumeration
• scientific article; zbMATH DE number 1538127 (Why is no real title available?)
• Complexity and algorithms for computing Voronoi cells of lattices
• Forbidden vertices
• scientific article; zbMATH DE number 7378671 (Why is no real title available?)
• The harmonic polytope
• A framework for the complexity of high-multiplicity scheduling problems
• scientific article; zbMATH DE number 1629817 (Why is no real title available?)
• Error control in polytope computations
• Approximate vertex enumeration
• On the complexity of some basic problems in computational convexity. I. Containment problems
• Enumerating vertices of covering polyhedra with totally unimodular constraint matrices
• Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces
• scientific article; zbMATH DE number 2040941 (Why is no real title available?)
• Beneath-and-Beyond revisited
• Enumerating vertices of \(0/1\)-polyhedra associated with \(0/1\)-totally unimodular matrices
• Optimizing the double description method for normal surface enumeration
• Bounds on the number of vertices of perturbed polyhedra
• How good are convex hull algorithms?
• A new algorithm to find all vertices of a polytope
• Sufficient optimality criterion for linearly constrained, separable concave minimization problems
• A portable parallel implementation of the \textit{lrs} vertex enumeration code
• A general algorithm for determining all essential solutions and inequalities for any convex polyhedron
• Farkas certificates and minimal witnesses for probabilistic reachability constraints

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)