Approximate inclusion-exclusion (Q1174115)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 8130
Language Label Description Also known as
default for all languages
No label defined
    English
    Approximate inclusion-exclusion
    scientific article; zbMATH DE number 8130

      Statements

      Approximate inclusion-exclusion (English)
      0 references
      0 references
      0 references
      25 June 1992
      0 references
      The inclusion-exclusion formula \[ | A_ 1\cup A_ 2\cup\dots\cup A_ n|=\sum_ i| A_ i| -\sum_{i<j}| A_ i\cap A_ j|+\sum_{i<j<k}| A_ i\cap A_ j\cap A_ k|-\dots+(- 1)^ n| A_ 1\cap\dots\cap A_ n|, \] may be used to find the size of the union with the fact that it has an exponential number of terms and that all terms are necessary. Moreover if the size of intersection of any sub-collection is missing then the size of union cannot be computed. In this paper the approximate size of the union when intersection sizes are known for only some of them, or when these quantities are given to within some error or both, have been estimated under certain conditions with several applications to Boolean functions.
      0 references
      inclusion-exclusion formula
      0 references
      0 references

      Identifiers