ROUNDING IN SYMMETRICAL MATRICES AND UNDIRECTED GRAPHS

We consider the problem of rounding the entries of a matrix without di storting the row, column, and grand totals. This problem arises in con trolling statistical disclosure, in data analysis, and elsewhere. Ther e are algorithms in the literature which produce roundings that are '' tight'' in the sense of distorting the totals very little. We concentr ate on the case of symmetric matrices. The existing algorithms do not preserve symmetry. In fact, the best symmetric rounding of a symmetric matrix may not be as tight as its best unsymmetric rounding. We sugge st three different relaxations of the tightness contraints, which admi t symmetric solutions. In each case we find the strongest possible res ult concerning the existence of a rounding of prescribed tightness. We also give efficient algorithms to determine if roundings with specifi ed distortion bounds exist and, if so, construct such a rounding. Thes e results and algorithms are based on a graph-theoretic model of the s ituation in which we are given an edge-weighted undirected graph and w e wish to round the edge weights so that the weight sums at any vertex , and the total weight sum over all edges, are changed as little as po ssible. We use graph factors as our main tool. As a consequence of our work on symmetric matrices we also provide more efficient algorithms for roundings in general matrices.