The optimal assignment problem for a countable state space Export

@article{citeulike:3890433, abstract = {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.}, archivePrefix = {arXiv}, author = {Akian, Marianne and Gaubert, Stephane and Kolokoltsov, Vassili}, citeulike-article-id = {3890433}, citeulike-linkout-0 = {http://arxiv.org/abs/0812.4866}, citeulike-linkout-1 = {http://arxiv.org/pdf/0812.4866}, day = {30}, eprint = {0812.4866}, keywords = {assignment, countable-set}, month = {Dec}, posted-at = {2009-01-16 09:13:21}, priority = {2}, title = {The optimal assignment problem for a countable state space}, url = {http://arxiv.org/abs/0812.4866}, year = {2008} }

TY - JOUR ID - citeulike:3890433 L3 - citeulike-article-id:3890433 N2 - 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. TI - The optimal assignment problem for a countable state space KW - assignment KW - countable-set AU - Akian, Marianne AU - Gaubert, Stephane AU - Kolokoltsov, Vassili PY - 2008/Dec/30/ UR - http://arxiv.org/abs/0812.4866 ER -