An Optimization Problem in Statistical Databases
Ljiljana Branković, Peter Horák, Mirka Miller · SIAM Journal on Discrete Mathematics · 2000
Let D={a 1 , . . ., a n } be a set of real numbers, and let $S\subset \{1,\ldots,n\}$. For an interval $I\subset \{1,\ldots,n\}$ we set SUM(I)=\sum_{i\in I}a_i$. In this paper we solve the following problem which has been asked in connection with security of statistical databases: Find a largest family B of subintervals of {1,. . .,n} so that knowing the value of SUM(I) for all $I\in {\bf B}$ does not enable one to calculate any element $a_i\in D$, where $i\in S$.