Comment Obscuring data using graph theory (Score 3) 126
One application of the famous min cut/max flow algorithm in graph theory (wooo!) is to consistently round matrix entries. i.e. (tricky definition) The rows sums and column sums of the rounded elements in the matrix are equal to the rounded row and column sums of the unaltered elements of the matrix.
I hear you asking. Who cares?
One application of this sort of matrix rounding is
publishing confidential survey data. Rounding can disguise the data, so that it is not traceable to any particular individual.
The reference below describes that the class of matrix rounding problems is equivalent to the flow problem in certain capacitated network flow models. Feasible flows can be found using the 'min cut/max flow' algorithm. The author proves that there is always a feasible solution for a subclass where marginal totals are uniformly confined.
reference:
Management Science, Vol. 12, No. 9, May 1966
Bacharach, Michael. "Matrix Rounding Problems"
since it is an old reference, I will attempt to convey the setup. The network is constructed as follows:
The matrix to round, A, has individual entries, A(ij) arranged in rows and columns...
Make a set X, consisting of a node, i, for each row in the matrix. Make a set Y consisting of a node, j, for each column in the matrix.
Add an arc (i,j) representing each matrix entry A(ij). (Note X union Y is a bipartite graph)
Add a source node s and attach it to each element in X, and a sink node t and attach it to each element in Y, the resulting arcs (s,i) represent each row sum and arcs (j,t) each column sum. The lower and upper bounds for all arcs should correspond to the lower and upper rounding limits of the original matrix entry, or the rounding limits for each row/column sum as appropriate.
Any feasible (integer) flow from s to t, will correspond to an acceptable (integer) rounding of values. (And a maximum flow will give us a feasible flow.)
I hear you asking. Who cares?
One application of this sort of matrix rounding is
publishing confidential survey data. Rounding can disguise the data, so that it is not traceable to any particular individual.
The reference below describes that the class of matrix rounding problems is equivalent to the flow problem in certain capacitated network flow models. Feasible flows can be found using the 'min cut/max flow' algorithm. The author proves that there is always a feasible solution for a subclass where marginal totals are uniformly confined.
reference:
Management Science, Vol. 12, No. 9, May 1966
Bacharach, Michael. "Matrix Rounding Problems"
since it is an old reference, I will attempt to convey the setup. The network is constructed as follows:
The matrix to round, A, has individual entries, A(ij) arranged in rows and columns...
Make a set X, consisting of a node, i, for each row in the matrix. Make a set Y consisting of a node, j, for each column in the matrix.
Add an arc (i,j) representing each matrix entry A(ij). (Note X union Y is a bipartite graph)
Add a source node s and attach it to each element in X, and a sink node t and attach it to each element in Y, the resulting arcs (s,i) represent each row sum and arcs (j,t) each column sum. The lower and upper bounds for all arcs should correspond to the lower and upper rounding limits of the original matrix entry, or the rounding limits for each row/column sum as appropriate.
Any feasible (integer) flow from s to t, will correspond to an acceptable (integer) rounding of values. (And a maximum flow will give us a feasible flow.)
