| Title: |
LEONTIEF SUBSTITUTION SYSTEMS AND MATROID COMPLEXES. |
| Authors: |
Provan, J. Scott; Billera, Louis J. |
| Source: |
Mathematics of Operations Research (INFORMS). Feb82, Vol. 7 Issue 1, p81-87. 7p. |
| Subject Terms: |
Linear systems; Set theory; Polyhedra |
| Abstract: |
A (pre-) Leontief substitution system is a linear system Ax = b, x > 0, where b is a nonnegative vector and A is a matrix containing at most one positive element :in each column. We investigate the face structure of nondegenerate Leontief substitution systems by looking at the corresponding dual simplicial complex. A characterization of the face structure is given for the bounded case (called a totally pre-Leontief substitution system by Dantzig and Veinott). and it is shown that the dual complex always comprises the independent sets of a matroid. Conversely, a characterization is given for the class of matroids whose independent sets form the dual complex to a polyhedron, and it is shown that this polyhedron can always be chosen to be a (not necessarily bounded) Leontief substitution system. The number of such matroids is also given as functions of the rank and the cardinality of the base set, and the number of nondegenerate totally (pre-) Leontief substitution systems is given as functions of the number of equalities and the number of variables. [ABSTRACT FROM AUTHOR] |
| : |
Copyright of Mathematics of Operations Research (INFORMS) is the property of INFORMS: Institute for Operations Research & the Management Sciences and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Business Source Premier |