Linear

Max-linear Systems: Theory and Algorithms by Peter Butkovič

By Peter Butkovič

Recent years have noticeable an important upward push of curiosity in max-linear concept and methods. as well as offering the linear-algebraic history within the box of tropical arithmetic, max-algebra offers mathematical idea and strategies for fixing numerous nonlinear difficulties coming up in parts corresponding to production, transportation, allocation of assets and knowledge processing know-how. it really is, consequently, an important subject spanning either natural and utilized mathematical fields.

A welcome creation to the topic of max-plus (tropical) linear algebra, and specifically algorithmic difficulties, Max-linear platforms: concept and Algorithms bargains a consolidation of either new and current literature, hence filling a much-needed hole. delivering the basics of max-algebraic thought in a finished and unified shape, as well as extra complex fabric with an emphasis on feasibility and reachability, this e-book provides a few new study effects. themes coated diversity from max-linear structures and the eigenvalue-eigenvector challenge to periodic habit of matrices, max-linear courses, linear independence, and matrix scaling.

This e-book assumes no previous wisdom of max-algebra and lots more and plenty of the theoryis illustrated with numerical examples, complemented via routines, and followed via either sensible and theoretical functions. Open difficulties also are established.

A clean and pioneering method of the subject of Max-linear structures, this booklet will carry a wide-ranging readership, and may be precious for:

• an individual with uncomplicated mathematical wisdom wishing to benefit crucial max-algebraic rules and methods

• undergraduate and postgraduate scholars of arithmetic or a comparable measure

• arithmetic researchers

• mathematicians operating in undefined, trade or management

Show description

Read or Download Max-linear Systems: Theory and Algorithms PDF

Similar linear books

Max-linear Systems: Theory and Algorithms

Contemporary years have visible an important upward push of curiosity in max-linear idea and methods. as well as offering the linear-algebraic historical past within the box of tropical arithmetic, max-algebra presents mathematical conception and methods for fixing a number of nonlinear difficulties coming up in parts comparable to production, transportation, allocation of assets and knowledge processing expertise.

Additional info for Max-linear Systems: Theory and Algorithms

Sample text

Only if”: Let y be a solution. 25 w ≤ A∗ ⊗ u and so y = A ⊗ w ≤ A ⊗ A∗ ⊗ u = b. Since yk ∈ Z for k ∈ J we also have ˜ A ⊗ w = y ≤ b. 1 then ˆ l ≤ y = A ⊗ w ≤ A ⊗ A∗ ⊗ b˜ = x. 9 as above, hence xˆ is the greatest solution. 7)T and J = {1, 3} (l is not specified). 8, 4)T . 10 xˆ is the greatest solution to the BMISDI provided that l ≤ xˆ (otherwise there is no solution). 2 Max-algebra and Combinatorial Optimization There is a number of combinatorial and combinatorial optimization problems closely related to max-algebra.

3. 1. 4 enables us to compile the following algorithm. 5 BMISDI Input: B ∈ Rn×n , u, l ∈ Rn and J ⊆ N . 2) or an indication that no such vector exists. 1. 2. 3. 4. 5. A := (B), x := u xj := xj for j ∈ J z := A∗ ⊗ x, x := A ⊗ z If l x then stop (no solution) If l ≤ x and xj ∈ Z for j ∈ J then stop else go to 2. 6 [30] The algorithm BMISDI is correct and requires O(n3 + n2 L) operations of addition, maximum, minimum, comparison and integer part, where L= j ∈J uj − lj . 4. 26 and hence x = A ⊗ z ≤ u if it terminates at step 5.

The permanent plays a key role in a number of max-algebraic problems because of the absence of the determinant due to the lack of subtraction. It turns out that the structure of the set of optimal solutions is related to some max-algebraic properties, in particular to questions such as the regularity of matrices. 31 If ⎛ ⎞ 3 7 2 A = ⎝4 1 5⎠ 2 6 3 then maper(A) = 14, ap(A) = {(123), (1)(23), (12)(3)}. A very simple property, on which the Hungarian method is based, is that the set of optimal solutions to the assignment problem for A does not change by adding a constant to a row or column of A.

Download PDF sample

Rated 4.32 of 5 – based on 27 votes