Volume 18, No 3, 2011, P. 1120
UDC 519.8
E. Kh. Gimadi, V. T. Dementiev
Probabilistic analysis of decentralized version of îne generalization of the assignment problem
Abstract:
A decentralized version of the SemiAssignment 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.
Keywords: decentralized transportation problem, NPhardness, approximation algorithm, asymptotic optimality, Petrov’s theorem, uniform distribution.
Gimadi Eduard Khirutdinovich ^{1,2}
Dementev Vladimir Tikhonovich ^{1,2}
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2.
Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
email: gimadi@math.nsc.ru, dementev@math.nsc.ru
