## Submodularity and pairwise independence

In this paper, we provide a characterization of the expected value of submodular set functions with pairwise independent random input. The set of pairwise independent (uncorrelated) probability distributions contains the mutually independent distribution and is contained within the set of arbitrarily dependent (correlated) distributions. We study the ratio of the maximum expected value of a … Read more