\documentclass[12pt]{article}
\begin{document}
%Zimmermann
%Karel","Karel.Zimmermann@mff.cuni.cz","
\section*{Solving two-sided (max,plus)-linear equation systems.} By {\sl Karel Zimmermann}.  

\medskip  \noindent Systems of equations of the following form will be considered: \begin{equation}\label{e1}  a_i(x) = b_i(x) ~ i \in I, \end{equation} where $I = \{1,\ldots, m\}, ~ J = \{1, \ldots, m\}$,  $$a_i(x) = max_{j \in J}(a_{ij} + x_j), ~ b_i(x) = max_{j \in J}(b_{ij} + x_j)~~ \forall i \in I$$ and $a_{ij},~b_{ij}$ are given real numbers.  \newline The aim of the contribution is to propose a polynomial method for solving system (\ref{e1}). Let $M$ be the set of all solutions of (\ref{e1}), let $M(\overline{x})$ denote the set of solutions of system (\ref{e1}) satisfying the additional constraint $x \leq \overline{x}$, where $ \overline{x}$ is a given fixed element of $R^n$. The proposed method either finds the maximum element of the set $M(\overline{x})$ (i.e. element $ \hat{x} \in M(\overline{x}) $, for which $x \in M(\overline{x})$ implies $ x~ \leq \hat{x}$), or finds out that $M(\overline{x}) = \emptyset $. The results are based on the following properties of system (\ref{e1}) (to simplify the notations we will assume in the sequel w.l.o.g. that $a_i(\overline{x}) \geq b_i(\overline{x})~~ \forall~~ i \in I$ and $\overline{x} \not \in M(\overline{x})$): \newline \newline (i) $M(\overline{x}) ~=~ \emptyset~ \Rightarrow M ~ = ~ \emptyset$.  \newline (ii) Let $K_i = \{ k \in J~;~ a_{ik}\leq b_{ik}\}~ \forall i \in I$. If for some $i_0 \in I$ the set $K_{i_0} = \emptyset$, then  $M(\overline{x})= \emptyset$. \newline (iii) Let $\beta_i(\overline{x}) = max_{k \in K_i}(b_{ik} + \overline{x}_k)$, $L_i(\overline{x}) = \{ j \in J~;~ a_{ij} + \overline{x}_j ~>~ \beta_i(\overline{x})\}$, $~ \forall~ i \in I$. If $\bigcup_{i \in I}L_i(\overline{x}) = J$, then $M(\overline{x})= \emptyset$. \newline (iv) Let $V_j(\overline{x}) = \{ i \in I ; j \in L_i(\overline{x}) \}$, let $ \overline{x}_j^{(1)} = min_{i \in V_j(\overline{x})}(\beta_i(\overline{x})- a_{ij})$ for all $j \in J$, for which $V_j(\overline{x}) \neq \emptyset$ and $ \overline{x}_j^{(1)} = \overline{x}_j $  otherwise. Let $\beta_i(\overline{x}^{(1)})~<~ \beta_i(\overline{x})$ for all $i \in I$. Then for at least one $i \in I$ the value $\beta_i(\overline{x}^{(1)})$ is equal to at least one of the threshold values $b_{ij} + \overline{x}_j ~< ~\beta_i(\overline{x})$. \newline \newline The method successively determines variables, which have to be decreased if equalities in (\ref{e1}) should be reached. If all variables have to be set in movement, no solution of (\ref{e1}) exists. If the set of unchanged variables is nonempty, the maximum element of (\ref{e1}) is obtained. Using these properties a polynomial behavior of the proposed method can be proved (in case of rational or integer inputs). Possibilities of further generalizations  and usage in optimization with constraints (\ref{e1}), as well as applications to synchronization problems will be briefly discussed.
%max algebra, (max,plus)-linear systems of equations, operations research.","65H10","15A78","for Max-algebra, MS7","16:48:33","Thu Mar 27 2008","83.148.5.94"
\end{document}
 zzzz
