Generators, extremals and bases of max cones
From MaRDI portal
Publication:869908
DOI10.1016/J.LAA.2006.10.004zbMATH Open1119.15018arXivmath/0604454OpenAlexW2100439831WikidataQ105580798 ScholiaQ105580798MaRDI QIDQ869908FDOQ869908
Authors: Hans Schneider, Peter Butkovič, Sergey M. Sergeev 
Publication date: 9 March 2007
Published in: Linear Algebra and its Applications (Search for Journal in Brave)
Abstract: Max cones are max-algebraic analogs of convex cones. In the present paper we develop a theory of generating sets and extremals of max cones in . 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.
Full work available at URL: https://arxiv.org/abs/math/0604454
Recommendations
Positive matrices and their generalizations; cones of matrices (15B48) Algebraic systems of matrices (15A30)
Cites Work
- Title not available (Why is that?)
- Tropical convexity
- Title not available (Why is that?)
- Linear and combinatorial optimization in ordered algebraic structures
- Minimax algebra and applications
- Title not available (Why is that?)
- Projections in minimax algebra
- Moduloïds and pseudomodules. I: Dimension theory
- Analysis and optimization of systems. (Proceedings of the 8th international conference organized by INRIA, June 8-10, 1988 in Antibes, France)
- Max-algebra: The linear algebra of combinatorics?
- Title not available (Why is that?)
- On Finding the Maxima of a Set of Vectors
- Tropical halfspaces
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Idempotent Mathematics and Mathematical Physics
- Bases in max-algebra
- Title not available (Why is that?)
- Tropical convexity via cellular resolutions
- Max-Plus Convex Geometry
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (54)
- Triangulation of diagonally dominant min-plus matrices
- On the set-estimation of uncertain max-plus linear systems
- Independence and orthogonality of algebraic eigenvectors over the max-plus algebra
- Tropical polar cones, hypergraph transversals, and mean payoff games
- On common eigenvectors for semigroups of matrices in tropical and traditional linear algebra
- Polynomially solvable special cases of the quadratic bottleneck assignment problem
- Tropical reproducing kernels and optimization
- Computation of the transient in max-plus linear systems via SMT-solving
- On tropical supereigenvectors
- Rank functions of tropical matrices
- Basic solutions of systems with two max-linear inequalities
- Tropical Fourier-Motzkin elimination, with an application to real-time verification
- The tropical analogue of polar cones
- The Whitney embedding theorem for tropical torsion modules. Classification of tropical modules
- A polynomial algorithm for solving system of inequalities in max-plus algebra
- Max algebraic powers of irreducible matrices in the periodic regime: an application of cyclic classes
- Barabanov norms, Lipschitz continuity and monotonicity for the max algebraic joint spectral radius
- Minimal half-spaces and external representation of tropical polyhedra
- A decomposition formula of idempotent polyhedral cones based on idempotent superharmonic spaces
- On the vectors associated with the roots of max-plus characteristic polynomials.
- Finding a bounded mixed-integer solution to a system of dual network inequalities
- On visualization scaling, subeigenvectors and Kleene stars in max algebra
- The number of extreme points of tropical polyhedra
- Bases in max-algebra
- Reachability analysis for timed automata using max-plus algebra
- \(\mathbf{X}\)-simple image eigencones of tropical matrices
- Tropical matrix groups
- Max-algebraic attraction cones of nonnegative irreducible matrices
- Extension of free sets over commutative semirings
- Computing the vertices of tropical polyhedra using directed hypergraphs
- Convexity of tropical polytopes
- Pure dimension and projectivity of tropical polytopes
- On \(2 \times 2\) tropical commuting matrices
- The geometric structure of max-plus hemispaces
- Tropical linear algebra with the Łukasiewicz t-norm
- Representation of max-plus convex sets in terms of extreme points and extreme generators
- Quasi-Euclidean classification of alcoved convex polyhedra
- Extremals of the supereigenvector cone in max algebra: a combinatorial description
- Tropicalization of facets of polytopes
- Tropical Gaussians: a brief survey
- Cyclic projectors and separation theorems in idempotent convex geometry
- Tropical polyhedra are equivalent to mean payoff games
- Orthogonality for \((0, -1)\) tropical normal matrices
- On tropical Kleene star matrices and alcoved polytopes
- Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria
- A characterization of bases of tropical kernels in terms of Cramer's rule
- Two cores of a nonnegative matrix
- On max-plus two-sided linear systems whose solution sets are min-plus linear
- L-Infinity Optimization to Bergman Fans of Matroids with an Application to Phylogenetics
- Characterization of tropical hemispaces by \((P, R)\)-decompositions
- Sur les génératrices extrémales de certains cônes de formes quadratiques doublement positives
- Tropical planar networks
- Inferring Min and Max Invariants Using Max-Plus Polyhedra
- The characterizations of irreducible matrices with proper supereigenvectors
Uses Software
This page was built for publication: Generators, extremals and bases of max cones
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q869908)
