G-2008-67
Tropical Cones Defined by Max-Linear Inequalities
, , , and BibTeX reference
We consider an inequality of the type over the idempotent semifield , where A,B are matrices of size m x n with coefficients in , and try to determine the set of its solutions. For the case m=1, we show that, for every , the set of solutions to a single inequality with , and form a semi-module of dimension , and determine its basis, where k<\i> is the number of . We give the necessary and sufficient conditions for the solution to be non trivial for the cases , and . We also show that, for m=2, the complexity of the problem (i.e. the number of cases to consider) is O($n^4$), and show how the solutions may be computed. We conclude the paper with two examples for m=2, n=7, and m=n=3, respectively.
Published September 2008 , 22 pages