A natural notion of morphism for linear programming problems. (English) Zbl 0683.90049
Summary: We present a morphism for linear programming problems, called the block reduction and construct the category \(LP^*\) which has block reductions as morphisms and linear programming problems as objects. The block reduction is a natural notion of morphism for linear programming problems in that it is an extension of the flow morphism for network flow problems [presented by L. H. Harper in Adv. Appl. Math. 1, 158-181 (1980; Zbl 0469.90028)], and at the same time it is a restriction of the reduction on linear programs (presented by L. H. Harper in J. Comb. Theory, Ser. A 32, 281-298 (1982; Zbl 0488.90045)]. After establishing this, we prove the existence of pushouts for block reductions.
References:
| [1] | Dantzig, G. B., Linear Programming and Extensions (1963), Princeton Univ. Press: Princeton Univ. Press Princeton, NJ · Zbl 0108.33103 |
| [2] | Feller, W., (An Introduction to Probability Theory and Its Applications, Vol. 1 (1959), Wiley: Wiley New York) · Zbl 0138.10207 |
| [3] | Gale, D.; Kuhn, H. W.; Tucker, A. W., Reductions of game matrices, (Kuhn; Tucker, Contributions to the Theory of Games, Vol. 1 (1950), Princeton Univ. Press: Princeton Univ. Press NJ) · Zbl 0041.25504 |
| [4] | Gray, J. W., Intrinsic linear programming, Adv. in Appl. Math., 6, 85-112 (1985) · Zbl 0594.90094 |
| [5] | Harper, L. H., Linear programming, the global approach, J. Combin. Theory Ser. A, 32, 281-298 (1982) · Zbl 0488.90045 |
| [6] | Harper, L. H., The global theory of flows in networks, Adv. in Appl. Math., 1, 158-181 (1980) · Zbl 0469.90028 |
| [7] | Harper, L. H.; Berenguer, X., The global theory of paths in networks, Adv. in Appl. Math., 2, 490-506 (1981) · Zbl 0491.90088 |
| [8] | Harper, L. H., The morphology of partially ordered sets, J. Combin. Theory, 17, 44-57 (1974) · Zbl 0297.05003 |
| [9] | Lawler, E. L., Combinatorial Optimization: Networks and Matroids (1976), Holt, Rinehart, & Winston: Holt, Rinehart, & Winston New York · Zbl 0358.68059 |
| [10] | MacLane, S., Categories for the Working Mathematician (1971), Springer-Verlag: Springer-Verlag New York · Zbl 0232.18001 |
| [11] | Wareham, A. K., Product Functors and Related Structures in the Category of Networks and Flow-Morphisms, (Doctoral dissertation (1980), University of California: University of California Riverside) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
