Generators, extremals and bases of max cones. (English) Zbl 1119.15018

Authors’ summary: Max cones are max-algebraic analogs of convex cones. We develop a theory of generating sets and extremals of max cones in \(\mathbb R_{+}^n\). This theory is based on the observation that extremals are minimal elements of max cones under suitable scalings of vectors. We give new proofs of existing results suitably generalizing, restating and refining them. Of these, it is important that any set of generators may be partitioned into the set of extremals and the set of redundant elements. We include results on properties of open and closed cones, on properties of totally dependent sets and on computational bounds for the problem of finding the (essentially unique) basis of a finitely generated cone.


15B48 Positive matrices and their generalizations; cones of matrices
15A30 Algebraic systems of matrices


Full Text: DOI arXiv


[1] M. Akian, S. Gaubert, V. Kolokoltsov, Set coverings and invertibility of the functional Galois connections, in: [20], pp. 19-51. Also <arXiv:math.FA/0403441>. · Zbl 1080.06001
[2] Baccelli, F.L.; Cohen, G.; Olsder, G.J.; Quadrat, J.P., Synchronization and linearity, (1992), J. Wiley and Sons Chichester, New York
[3] F. Block, J. Yu, Tropical convexity via cellular resolutions, <arXiv:math.MG/0503279>. · Zbl 1097.52506
[4] Bourbaki, N., LES structures fundamentales de l’analyse, livre II, chap. II, (1947), Herman Paris
[5] Butkovič, P., MAX-algebra: the linear algebra of combinatorics?, Linear algebra appl., 367, 313-335, (2003) · Zbl 1022.15017
[6] G. Cohen, S. Gaubert, J.P. Quadrat, I. Singer, Max-plus convex sets and functions, in: [20], pp. 105-129. Also <arXiv:math.FA/0308166>. · Zbl 1093.26005
[7] Cuninghame-Green, R.A., Process of synchronization in steelworks – a problem of feasibility, (), 323-328
[8] Cuninghame-Green, R.A., Projections in minimax algebra, Math. programm., 10, 1, 111-123, (1976) · Zbl 0336.90062
[9] Cuninghame-Green, R.A., Minimax algebra, Lecture notes in economics and mathematical systems, vol. 166, (1979), Springer Berlin
[10] Cuninghame-Green, R.A., Minimax algebra and applications, Advances in imaging and electron physics, vol. 90, (1995), Academic Press New York, pp. 1-121
[11] Cuninghame-Green, R.A.; Butkovič, P., Bases in MAX-algebra, Linear algebra appl., 389, 107-120, (2004) · Zbl 1059.15001
[12] Develin, M.; Sturmfels, B., Tropical convexity, Documenta math., 9, 1-27, (2004), Also · Zbl 1054.52004
[13] Gaubert, S.; Katz, R., MAX-plus convex geometry, (), 192-206, · Zbl 1134.52303
[14] S. Gaubert, R. Katz, The Minkowski theorem for max-plus convex sets, Linear Algebra Appl. (this issue). Also <arXiv:math.GM/0605078>.
[15] S. Gaubert, M.P. Scilab, Max-plus linear algebra with Scilab, ALAPEDES Max-plus Software Workshop, INRIA, June 1998. Available from: <http://www.scilab.org> as file mxpcourse.ps in the MAXPLUS2.3.3 toolbox (via path Contributions→Download→Modeling and Control Tools→MAXPLUS2.3.3 for Scilab 3.1.1).
[16] Gondran, M.; Minoux, M., Linear algebra of dioïds: a survey of recent results, Ann. discrete math., 19, 147-164, (1984) · Zbl 0568.08001
[17] Helbig, S., Carathéodory’s and krei˘n-milman’s theorems in fully ordered groups, Comment. univ. carolin., 29, 157-167, (1988) · Zbl 0652.06010
[18] M. Joswig, Tropical halfspaces, <arXiv:math.CO/0312068>. · Zbl 1090.52500
[19] Kung, H.T.; Luccio, F.; Preparata, F.P., On finding the maxima of a set of vectors, J. assoc. comput. Mach., 22, 4, 469-476, (1975) · Zbl 0316.68030
[20] Litvinov, G.; Maslov, V., ()
[21] Preparata, F.P.; Shamos, M., Computational geometry. an introduction, (1985), Springer New York · Zbl 0759.68037
[22] Rockafellar, R.T., Convex analysis, (1970), Princeton University Press · Zbl 0229.90020
[23] S. Sergeev, Max-plus definite matrix closures and their eigenspaces, this issue. Also <arXiv:math.MG/0506177>.
[24] Vorob’yev, N.N., Extremal algebra of positive matrices, Elektron. informationsverarb. kybernetik, 3, 39-71, (1967), (in Russian)
[25] Wagneur, E., Finitely generated moduloïds: the existence and unicity problem for bases, (), 966-976
[26] Wagneur, E., Moduloïds and pseudomodules. 1. dimension theory, Discrete math., 98, 57-73, (1991) · Zbl 0757.06008
[27] Zimmermann, K., A general separation theorem in extremal algebras, Ekonom.-mat. obzor, 13, 2, 179-201, (1977)
[28] Zimmermann, U., Linear and combinatorial optimization in ordered algebraic structures, Annals of discrete mathematics, vol. 10, (1981), North Holland Amsterdam · Zbl 0466.90045
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.