correlation gap – Optimization Online

Submodularity, pairwise independence and correlation gap

Published: 2022/09/18, Updated: 2023/12/20

Optimization in Data Science, Robust Optimization, Stochastic Programming correlation gap, distributionally robust optimization, linear programming, mechanism design, pairwise independence, submodularity

In this paper, we provide a characterization of the expected value of monotone submodular set functions with $n$ pairwise independent random inputs. Inspired by the notion of “correlation gap”, we study the ratio of the maximum expected value of a function with arbitrary dependence among the random inputs with given marginal probabilities to the maximum … Read more

Tight Probability Bounds with Pairwise Independence

Published: 2022/04/29, Updated: 2023/12/20

Arjun Ramachandra

Karthik Natarajan

Applications - OR and Management Sciences, Combinatorial Optimization, Linear Programming bivariate feasibility, correlation gap, discrete optimization, distributionally robust bottleneck optimization, linear programming, pairwise independence, probability bounds, submodular functions, uncorrelated random inputs

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 probability … Read more