Mathematics – Optimization and Control
Scientific paper
2008-12-30
Proceedings of the International Conference on Tropical and Idempotent Mathematics, G.L. Litvinov and S.N. Sergeev Eds, volume
Mathematics
Optimization and Control
22 pages
Scientific paper
Given a square matrix B=(b_{ij}) with real entries, the optimal assignment problem is to find a bijection s between the rows and the columns maximising the sum of the b_{is(i)}. In discrete optimal control and in the theory of discrete event systems, one often encounters the problem of solving the equation Bf=g for a given vector g, where the same symbol B denotes the corresponding max-plus linear operator, (Bf)_i:=max_j (b_{ij}+f_j). The matrix B is said to be strongly regular when there exists a vector g such that the equation Bf=g has a unique solution f. A result of Butkovic and Hevery shows that B is strongly regular if and only if the associated optimal assignment problem has a unique solution. We establish here an extension of this result which applies to max-plus linear operators over a countable state space. The proofs use the theory developed in a previous work in which we characterised the unique solvability of equations involving Moreau conjugacies over an infinite state space, in terms of the minimality of certain coverings of the state space by generalised subdifferentials.
Akian Marianne
Gaubert Stephane
Kolokoltsov Vassili
No associations
LandOfFree
The optimal assignment problem for a countable state space does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The optimal assignment problem for a countable state space, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The optimal assignment problem for a countable state space will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-117198