zbMATH — the first resource for mathematics

The equation $$A \otimes x = B \otimes y$$ over $$(\max,+)$$. (English) Zbl 1021.65022
This paper deals with the two-sided homogeneous system of linear equations $$A\otimes x= B\otimes y$$ over $$(\max,+)$$ with no infinite rows or columns in $$A$$ or $$B$$. Such system arises from the synchronization problem. A straight-forward algorithm is presented. This algorithm converges to a solution in pseudopolynomial time from any finite initial pair whenever a solution exists.
It is of interest to note that this algorithm can be used to seek finite solutions for instance of the related inhomogeneous equation $$A\otimes x\oplus a= B\otimes x\oplus b$$. By the way, if the finite elements of $$A$$, $$B$$ are all integers, convergence is in a finite number of steps.

MSC:
 65F30 Other matrix algorithms (MSC2010) 15A80 Max-plus and related algebras 15A06 Linear equations (linear algebraic aspects)
Full Text:
References:
  Baccelli, F.L.; Cohen, G.; Olsder, G.-J.; Quadrat, J.-P., Synchronization and linearity, (1992), Wiley New York  Butkovic, P.; Hegedüs, G., An elimination method for finding all solutions of the system of linear equations over an extremal algebra, Ekonom. mat. obzor., 20, 203-214, (1984)  R.A. Cuninghame-Green, Minimax algebra, Lecture Notes in Economics and Mathematical Systems, No. 166, Springer, Berlin, 1979.  Walkup, E.A.; Borriello, G., A general linear MAX-plus solution technique, (), 406-415 · Zbl 0898.68035  U. Zimmermann, Linear and combinatorial optimization in ordered algebraic structures, Ann. Discrete Math. (10) (1981). · 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.