The problem of integer-valued balancing of a three-dimensional matrix and algorithms of its solution
Modelirovanie i analiz informacionnyh sistem, Tome 17 (2010) no. 2, pp. 72-98
Voir la notice de l'article provenant de la source Math-Net.Ru
The article is devoted to the problem of integer-valued balancing of a three-dimensional matrix. The reduction of this problem to the problem of finding a maximum flow in the multiple network of integer-valued balancing and the algorithm for this problem are suggested. Also, the comparative characteristic of two algorithms of integer-valued balancing is made according to the results of the computing experiments. NP-completeness of the problem of integer-valued balancing of a three-dimensional matrix is proved in the article. The problem of minimization of the errors of rounding off in the problem of integer-valued balancing is explored.
Keywords:
integer-valued balancing, three-dimensional matrices, multiple networks, multiple flows, generalized labeling algorithm, first Gomory algorithm, $NP$-completeness, minimization of the errors of rounding off.
@article{MAIS_2010_17_2_a4,
author = {V. S. Rublev and A. V. Smirnov},
title = {The problem of integer-valued balancing of a three-dimensional matrix and algorithms of its solution},
journal = {Modelirovanie i analiz informacionnyh sistem},
pages = {72--98},
publisher = {mathdoc},
volume = {17},
number = {2},
year = {2010},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/MAIS_2010_17_2_a4/}
}
TY - JOUR AU - V. S. Rublev AU - A. V. Smirnov TI - The problem of integer-valued balancing of a three-dimensional matrix and algorithms of its solution JO - Modelirovanie i analiz informacionnyh sistem PY - 2010 SP - 72 EP - 98 VL - 17 IS - 2 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/MAIS_2010_17_2_a4/ LA - ru ID - MAIS_2010_17_2_a4 ER -
%0 Journal Article %A V. S. Rublev %A A. V. Smirnov %T The problem of integer-valued balancing of a three-dimensional matrix and algorithms of its solution %J Modelirovanie i analiz informacionnyh sistem %D 2010 %P 72-98 %V 17 %N 2 %I mathdoc %U http://geodesic.mathdoc.fr/item/MAIS_2010_17_2_a4/ %G ru %F MAIS_2010_17_2_a4
V. S. Rublev; A. V. Smirnov. The problem of integer-valued balancing of a three-dimensional matrix and algorithms of its solution. Modelirovanie i analiz informacionnyh sistem, Tome 17 (2010) no. 2, pp. 72-98. http://geodesic.mathdoc.fr/item/MAIS_2010_17_2_a4/