Rounding in symmetric matrices and undirected graphs

We consider the problem of rounding the entries of a matrix without distorting the row, column, and grand totals. This problem arises in controlling statistical disclosure, in data analysis, and elsewhere. There are algorithms in the literature which produce roundings that are ''tight'' in the sense of distorting the totals very little. We concentrate 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 suggest three different relaxations of the tightness contraints, which admit symmetric solutions. In each case we find the strongest possible result concerning the existence of a rounding of prescribed tightness. We also give efficient algorithms to determine if roundings with specified distortion bounds exist and, if so, construct such a rounding. These results and algorithms are based on a graph-theoretic model of the situation in which we are given an edge-weighted undirected graph and we 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 possible. 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.