Table rounding problem

Abstract

From time to time, people dealing with accounting are faced with the following table rounding problem. Consider a m x n table with numerical values (e.g., amount of money) in which the last column contains check sums of numbers in particular rows. Similarly, the last row consists of column check sums. A new table is to be produced in which the original numbers, and check sums, are rounded off (e.g. to integers). However, the classical rounding procedure (e.g., rounding fractions smaller than 0.,5 down, otherwise up) can generally violate the validity of sums. Therefore, the possibility to round off the non-integer numbers in the table to adjacent integers (i.e., either up or down independently on their fractions) is explored in order to preserve the check sums. We formulate a necessary and sufficient condition stating when rounding, which is consistent with prescribed (integer) check sums, exists. We also prove that when rounding of check sums is not given as a part of the input and, at the same time, the sums are allowed to be rounded to adjacent integers such rounding always exists. Using maximum flow algorithm the required rounding can be found in both cases in polynomial time O((m + n)3) (provided that it exists). Moreover, rounding with the minimal sum of absolute round-errors is computed within O(mn(m + n)2) time.