A basis enumeration algorithm for linear systems with geometric applications

DOI10.1016/0893-9659(91)90141-HMaRDI QIDQ1180318zbMATH OpenFDO

Authors David Avis, Komei Fukuda

Publication date 27 June 1992

Published in Applied Mathematics Letters (Search for Journal in Brave)

zbMATH Keywords

linear systemconvex polyhedronenumeration of all basespivot-based algorithm

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Combinatorial aspects of matroids and geometric lattices (05B35)

Recommendations

• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• The Complexity of Vertex Enumeration Methods
• Combinatorial face enumeration in convex polytopes
• A POLYNOMIAL ALGORITHM FOR ENUMERATING ALL VERTICES OF A BASE POLYHEDRON

Cites work

• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 3497901 (Why is no real title available?)
• A combinatorial abstraction of linear programming
• A convergent criss-cross method
• A finite conformal-elimination free algorithm over oriented matroid programming
• A finite crisscross method for oriented matroids
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• On the finiteness of the criss-cross method
• The Complexity of Vertex Enumeration Methods

Cited in

(8)

• Reverse search for enumeration
• Output-sensitive cell enumeration in hyperplane arrangements
• Theory of uncontrollable flows -- a new type of network-flow theory as a model for the 21st century of multiple values
• An Enumerative Geometry Framework for Algorithmic Line Problems in $\mathbb R^3$
• An implementation for the algorithm of Janet bases of linear differential ideals in the Maple system
• scientific article; zbMATH DE number 2040941 (Why is no real title available?)
• Extended convex hull
• Tabu search and finite convergence

This page was built for publication: A basis enumeration algorithm for linear systems with geometric applications

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