Exponential behaviour of the Butkovič–Zimmermann algorithm for solving two-sided linear systems in max-algebra

In [P. Butkovič, K. Zimmermann, A strongly polynomial algorithm for solving two-sided linear systems in max-algebra, Discrete Applied Mathematics 154 (3) (2006) 437–446] an ingenious algorithm for solving systems of two-sided linear equations in max-algebra was given and claimed to be strongly polynomial. However, in this note we give a sequence of examples showing exponential behaviour of the algorithm. We conclude that the problem of finding a strongly polynomial algorithm is still open.