# Matrix Rounding

## The Basic Problem

We consider variations of the following matrix rounding problem. Given a matrix , compute an integer matrix such that the error in all rows and columns as well as in the whole matrix is small, i.e.,

for some small positive constants . In statistics, this problem with errors is known as Controlled Rounding and was first studied by Bacharach [1] and later by Causey, Cox and Ernst [5]. Here, one wants to round the entries of a table of frequency counts to a given base such that the totals of the table are not changed. This allows to increase the readability of tables (by rounding to multiples of ), but the main use is in confidentiality protection [12], where one wants to perturb the table such that no knowledge about individuals can be gained from small counts. In discrete mathematics, Baranyai [2] used such roundings for colouring and partitioning complete uniform hypergraphs.

## Extension I: Linear-Time One-Pass Quasi-Rounding

Another application of matrix rounding is the flexible transfer line scheduling problem [11,4]. Here one has a single machine that can produce different products, but only one at a time. It is known how many products of each type should be produced after steps. The goal is to design a production schedule such that the given number of goods is produced after steps. The crucial point is that this schedule should be balanced, i.e., after steps, approximately units of product should be produced.

We can encode the demands as a column vector of values . If is the -matrix given by repeating the above vector times, a good schedule is given by an integral matrix having small rounding error in all columns and in all initial row intervals.

In [7] we give a linear-time one-pass algorithm to compute a quasi-rounding for a given matrix with integral column sums. This quasi-rounding fulfils

Using the triangle inequality, one immediately gets that the error in a contiguous part of a row is less than two. This may also be desirable for controlled rounding, if the column labels of a table are ordered. In this case we can calculate the value for a range of entries while controlling the error.

## Extension II: Rounding Row and Column Intervals

For controlled rounding, a quasi-rounding as above does normally not suffice. Also, if both the rows and the columns of a table are ordered, one would like to control the error in initial column intervals, too. In other words, given a matrix , we seek for a matrix fulfilling

In [8] we give a time algorithm to compute such roundings. This algorithm is based on the observation that half-integral matrices (i.e., entries ) can easily be rounded. Adapting a method introduced by Beck and Spencer [3], it is possible to round matrices of binary numbers recursively by computing roundings of half-integral matrices.

## Extension III: Randomised Rounding

A rounding computed by a randomised algorithm is called unbiased [6,9] or randomised [10] rounding, if each entry is rounded up with probability equal to its fractional value. Such roundings have the property that the sum over a set of entries in has expected value equal to the sum over the corresponding entries in , hence the term unbiased''.

The algorithm from [8] can easily be modified to compute unbiased roundings by modifying the half-integral rounding algorithm accordingly. This algorithm will then compute an unbiased controlled rounding of a matrix containing -bit numbers in time .

## Bibliography

1
M. Bacharach.
Matrix rounding problems.
Management Science (Series A), 12:732-742, 1966.
2
Zs. Baranyai.
On the factorization of the complete uniform hypergraph.
In Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdös on his 60th birthday), Vol. I, pages 91-108. Colloq. Math. Soc. János Bolyai, Vol. 10. North-Holland, Amsterdam, 1975.
3
J. Beck and J. Spencer.
Well distributed 2-colorings of integers relative to long arithmetic progressions.
Acta Arithm., 43:287-298, 1984.
4
N. Brauner and Y. Crama.
The maximum deviation just-in-time scheduling problem.
Discrete Appl. Math., 134:25-50, 2004.
5
B. D. Causey, L. H. Cox, and L. R. Ernst.
Applications of transportation theory to statistical problems.
Journal of the American Statistical Association, 80(392):903-909, Dec 1985.
6
L. H. Cox.
A constructive procedure for unbiased controlled rounding.
Journal of the American Statistical Association, 82:520-524, 1987.
7
B. Doerr, T. Friedrich, C. Klein, and R. Osbild.
Rounding of sequences and matrices, with applications.
In Third Workshop on Approximation and Online Algorithms (WAOA), volume 3879 of Lecture Notes in Computer Science, pages 96-109. Springer, 2006.
8
B. Doerr, T. Friedrich, C. Klein, and R. Osbild.
Unbiased matrix rounding.
In 10th Scandinavian Workshop on Algorithm Theory (SWAT), volume 4059 of Lecture Notes in Computer Science, pages 102-112. Springer, 2006.
9
I. P. Fellegi.
Controlled random rounding.
Survey Methodology, 1:123-133, 1975.
10
P. Raghavan.
Probabilistic construction of deterministic algorithms: Approximating packing integer programs.
J. Comput. Syst. Sci., 37:130-143, 1988.
11
G. Steiner and S. Yeomans.
Level schedules for mixed-model, just-in-time processes.
Management Science, 39:728-735, 1993.
12
L. Willenborg and T. de Waal.
Elements of Statistical Disclosure Control, volume 155 of Lecture Notes in Statistics.
Springer, 2001.