pairwise independence

Submodularity and pairwise independence

  • Karthik Natarajan
  • Arjun Ramachandra
    • Categories Optimization in Data Science, Robust Optimization, Stochastic Programming Tags , , ,

    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

    Tight Probability Bounds with Pairwise Independence

  • Arjun Ramachandra
  • Karthik Natarajan
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Linear Programming Tags , , , , , , , ,

    \(\) While useful probability bounds for \(n\) pairwise independent Bernoulli random variables adding up to at least an integer \(k\) have been proposed in the literature, none of these bounds are tight in general. In this paper, we provide several results in this direction. Firstly, when \(k = 1\), the tightest upper bound on the … Read more