On the Transience of Linear Max-Plus Dynamical Systems

Details On the Transience of Linear Max-Plus Dynamical Systems On the Transience of Linear Max-Plus Dynamical Systems

2011-11-20

arxiv.org/abs/1111.4600v1

Computer Science

Discrete Mathematics

35 pages, 5 figures

Scientific paper

We study the transients of linear max-plus dynamical systems. For that, we consider for each irreducible max-plus matrix A, the weighted graph G(A) such that A is the adjacency matrix of G(A). Based on a novel graph-theoretic counterpart to the number-theoretic Brauer's theorem, we propose two new methods for the construction of arbitrarily long paths in G(A) with maximal weight. That leads to two new upper bounds on the transient of a linear max-plus system which both improve on the bounds previously given by Even and Rajsbaum (STOC 1990, Theory of Computing Systems 1997), by Bouillard and Gaujal (Research Report 2000), and by Soto y Koelemeijer (PhD Thesis 2003), and are, in general, incomparable with Hartmann and Arguelles' bound (Mathematics of Operations Research 1999). With our approach, we also show how to improve the latter bound by a factor of two. A significant benefit of our bounds is that each of them turns out to be linear in the size of the system in various classes of linear max-plus system whereas the bounds previously given are all at least quadratic. Our second result concerns the relationship between matrix and system transients: We prove that the transient of an NxN matrix A is, up to some constant, equal to the transient of an A-linear system with an initial vector whose norm is quadratic in N. Finally, we study the applicability of our results to the well-known Full Reversal algorithm whose behavior can be described as a min-plus linear system.

Affiliated with

Also associated with

No associations

Rating

On the Transience of Linear Max-Plus Dynamical Systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Transience of Linear Max-Plus Dynamical Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Transience of Linear Max-Plus Dynamical Systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-129847