This article is cited in 16 papers

The problem of integer-valued balancing of a three-dimensional matrix and algorithms of its solution

V. S. Rublev, A. V. Smirnov

P. G. Demidov Yaroslavl State University

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

UDC: 519.854.2

Received: 22.04.2010