Table rounding problem

From time to time, people dealing with accounting are faced with the follow ing 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 numbe rs in particular rows. Similarly, the last row consists of column check sum s. A new table is to be produced in which the original numbers, and check s ums are rounded off (e.g., to integers). However, the classical rounding pr ocedure (i.e., 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., eithe r up or down independently on their fractions) is explored in order to pres erve the check sums. We formulate a necessary and sufficient condition stat ing 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 algori thm 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 s um of absolute round-errors is computed within O(mn(m + n)(2)) time.