A common scenario is that one has a well-ordered universe, and one wishes to answer queries of the form "how many elements are at most x?". If one has d elements, then one can pick logd thresholds in a geometric sequence, save information on the sets smaller than the thresholds, and be able to approximately answer such queries. The question below deals with a similar scenario but in which one has a bunch of overlapping sets in the universe, and one has to pick thresholds in each. The issue is that when the sets are overlapping one might want to introduce non-trivial dependencies between the thresholds in different sets.

I have a well-ordered universe U of size m, and n (overlapping) subsets $S_1,...,S_n\subseteq U$, each of size $|S_i|=d$. For a subset $S_j$ and a number $1\leq i\leq d$ let $S_j^{i}$ be the set of the i smallest elements in $S_j$.

I'd like to pick as few $S_j^i$ as possible and ensure the following property: For any choice of $i_1,\ldots,i_n$ such that $S_{1}^{i_1}\cup...\cup S_n^{i_n}$ contains at least 10% of the elements in U, there are $i_1'\leq i_1,...,i_n'\leq i_n$, such that we picked $S_1^{i_1'},\ldots,S_n^{i_n'}$, and $S_{1}^{i_1'}\cup...\cup S_n^{i_n'}$ contains at least 5% of the elements in U.

Clearly, one can take all $n\cdot d$ possible sets. Are $n\cdot \log d$ sets sufficient?

  • $\begingroup$ I have two questions regarding your question. (1) Do you really want the property only for 10% or for every number? Because for 10% I'm not sure why not even $O(n)$ sets could be already sufficient. (2) If $S_{j_2'}^{i_2'}$ is contained in $S_{j_1}^{i_1}$, are we still no allowed to pick $i_2'$ if it is larger than $i_2$? $\endgroup$ – domotorp Mar 20 '15 at 11:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.