Probabilistic analysis of decentralized version of оne generalization of the assignment problem

A decentralized version of the Semi-Assignment problem is considered, when elements of $m\times n$-matrix are nonnegative, $m=kn$, $k$ is natural number. It is supposed, that $nk$ elements of the matrix are chosen: $k$ elements in each column and one element in each row in order to maximize the total sum of chosen elements. An approximation algorithm with $O(mn)$ time complexity is presented. In the case of inputs, when elements are independent random values with common uniform distribution function, the estimations of a relative error and a fault probability of the algorithm are obtained, and conditions of asymptotic optimality are established. Bibliogr. 8.