A uniform synchronization problem over max-plus algebra
- PDF / 314,863 Bytes
- 10 Pages / 439.37 x 666.142 pts Page_size
- 37 Downloads / 156 Views
A uniform synchronization problem over max-plus algebra AbdulKadir Datti1 · Abdulhadi Aminu2 Received: 1 October 2017 / Accepted: 26 September 2020 © African Mathematical Union and Springer-Verlag GmbH Deutschland, ein Teil von Springer Nature 2020
Abstract The solution of A ⊗ xB⊗y has been considered in the literature and various methods have been established. However, a solution such that the resulting product is a vector having all its components equal has not been treated to the best of our knowledge. In this paper, we study a synchronization problem A ⊗ xB ⊗ yα and proposed an O(mn + mk) algorithm for its solution. Where m is the number of rows of the matrices and n and k are the number of columns of A and B respectively. That is, given any Two matrices that have the same number of rows, m we introduce some algorithm that generates two column vectors x and y such that A ⊗ x B ⊗ y α, where A and B assumed to be P-doubly G-astic matrices having the same number of rows and α is a column vector having all its components equal. Keywords Max-plus algebra · O-plus · O-times · Doubly G-astic matrix Mathematics Subject Classification 15A06 · 15A80
1 Introduction Max-plus algebra is an algebraic structure in which a ⊕ b max{a, b} and a ⊗ b a + b ¯ R∪ are used instead of a + b and a × b as used in linear algebra, where a, b ∈ R {−∞}. It has been used in applications, such as the shortest route problem, airport problem, synchronization, project scheduling feasibility and reachability. See [4–6, 17]. The field of operational research emerged during the second world war as a scientific approach for decision making. One of the goals of the field is to search for optimal solution to a given problem. Max-plus algebra makes some of the complicated problems in classical linear algebra easier using the operation of taking maximum, thus making it best for describing problems in operational research. The study of max-plus algebra emerged soon after the field of operational research. This algebraic structure is a semiring over R ∪ {−∞}. The first attempt of a complete study of minimax algebra by Cuninghame-Green was not published until 1974, [12]. In some previous researches, max-algebra and some structures related to it have been considered. See [7, 8,
B
AbdulKadir Datti [email protected]
1
Department of Mathematics, Bauchi State University, Gadau, P.M.B 65, Gadau, Nigeria
2
Department of Mathematics, Kano University of Science and Technology, Wudil, P.M.B 3244, Kano, Nigeria
123
A. Datti, A. Aminu
11, 12, 15, 16, 20], where the system of linear equations over the structure have been treated. Also in [12], System of one-sided linear equation has been established. Eigenvector problem has been considered in other papers, such as in [12, 20]. Other research in the area are [4, 18], where some applications of the subject have been discussed. A necessary and sufficient condition for the existence of the solution of the system of equations has been established in [1]. In Cuninghame-Green and Butkovic [13]
Data Loading...
