
We develop an randomized approximation algorithm for the size of set union problem $\arrowvert A_1\cup A_2\cup...\cup A_m\arrowvert$, which given a list of sets $A_1,...,A_m$ with approximate set size $m_i$ for $A_i$ with $m_i\in \left((1-��_L)|A_i|, (1+��_R)|A_i|\right)$, and biased random generators with $Prob(x=\randomElm(A_i))\in \left[{1-��_L\over |A_i|},{1+��_R\over |A_i|}\right]$ for each input set $A_i$ and element $x\in A_i,$ where $i=1, 2, ..., m$. The approximation ratio for $\arrowvert A_1\cup A_2\cup...\cup A_m\arrowvert$ is in the range $[(1-��)(1-��_L)(1-��_L), (1+��)(1+��_R)(1+��_R)]$ for any $��\in (0,1)$, where $��_L, ��_R, ��_L,��_R\in (0,1)$. The complexity of the algorithm is measured by both time complexity, and round complexity. The algorithm is allowed to make multiple membership queries and get random elements from the input sets in one round. Our algorithm makes adaptive accesses to input sets with multiple rounds. Our algorithm gives an approximation scheme with $O(\setCount\cdot(\log \setCount)^{O(1)})$ running time and $O(\log m)$ rounds, where $m$ is the number of sets. Our algorithm can handle input sets that can generate random elements with bias, and its approximation ratio depends on the bias. Our algorithm gives a flexible tradeoff with time complexity $O\left(\setCount^{1+��}\right)$ and round complexity $O\left({1\over ��}\right)$ for any $��\in(0,1)$.
Computational Geometry (cs.CG), FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Randomized algorithms, Computational Complexity (cs.CC), Approximation algorithms, Computer Science - Computational Complexity, \#P-hardness, Computer Science - Data Structures and Algorithms, Computer Science - Computational Geometry, Analysis of algorithms, Data Structures and Algorithms (cs.DS), randomized approximation, rounds, lattice points, sublinear time, Computer Science - Discrete Mathematics
Computational Geometry (cs.CG), FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Randomized algorithms, Computational Complexity (cs.CC), Approximation algorithms, Computer Science - Computational Complexity, \#P-hardness, Computer Science - Data Structures and Algorithms, Computer Science - Computational Geometry, Analysis of algorithms, Data Structures and Algorithms (cs.DS), randomized approximation, rounds, lattice points, sublinear time, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
