RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Subscription Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Diskretn. Anal. Issled. Oper.: Year: Volume: Issue: Page: Find

 Diskretn. Anal. Issled. Oper., 2011, Volume 18, Number 3, Pages 11–20 (Mi da650)

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

E. Kh. Gimadiab, V. T. Dementevab

a S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia
b Novosibirsk State University, Novosibirsk, Russia

Abstract: 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.

Keywords: decentralized transportation problem, NP-hardness, approximation algorithm, asymptotic optimality, Petrov's theorem, uniform distribution.

Full text: PDF file (256 kB)
References: PDF file   HTML file

Bibliographic databases:
UDC: 519.8
Revised: 12.04.2011

Citation: E. Kh. Gimadi, V. T. Dementev, “Probabilistic analysis of decentralized version of îne generalization of the assignment problem”, Diskretn. Anal. Issled. Oper., 18:3 (2011), 11–20

Citation in format AMSBIB
\Bibitem{GimDem11} \by E.~Kh.~Gimadi, V.~T.~Dementev \paper Probabilistic analysis of decentralized version of îne generalization of the assignment problem \jour Diskretn. Anal. Issled. Oper. \yr 2011 \vol 18 \issue 3 \pages 11--20 \mathnet{http://mi.mathnet.ru/da650} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=2883264} \zmath{https://zbmath.org/?q=an:1249.90141}