A Note on Approximate Inclusion-Exclusion


Avraham A. Melkman
e-mail: melkman@cs.bgu.ac.il

Solomon Eyal Shimony
e-mail: shimony@cs.bgu.ac.il

Ben-Gurion University - Math. and Comp. Sci. Dept.
P. O. Box 653
84105 Be'er Sheva, Israel
FAX : +972-7-472909

Abstract (ASCII version):

Given a sequence of n sets, it was shown by Kahn, Linial and Samorodnitsky that if it is known that u, the size of the union of all the sets, is less than 2^(n-1), then it can be determined uniquely from just the sizes of the intersections (but without knowing the size of the intersection of all n sets). Since their proof was existential they posed the question of finding an adaptive procedure for determining $u$. Here we present such an algorithm, and discuss the proof of some exact bounds on the intersection sizes when the above conditions do not hold.


Inclusion-exclusion, DNF model counting.

Related Work:

Jeff Kahn, Nathan Linial, and Alex Samorodnitsky. Inclusion-exclusion: Exact and approximate. Combinatorica, (in print).

Nathan Linial and Noam Nisan. Approximate inclusion-exclusion. Combinatorica, 10:349-365, 1990.


Short version of paper - to appear in Discrete Applied Mathematics.

Long version of this paper is available in (PostScript) format.

shimony@cs.bgu.ac.il / Last update: 20 July 1996