Tight Probability Bounds with Pairwise Independence

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 towards finding tight probability bounds in this direction. Firstly, when $k = 1$, the tightest … Read more

Extremal Probability Bounds in Combinatorial Optimization

In this paper, we compute the tightest possible bounds on the probability that the optimal value of a combinatorial optimization problem in maximization form with a random objective exceeds a given number, assuming only knowledge of the marginal distributions of the objective coefficient vector. The bounds are “extremal” since they are valid across all joint … Read more

Robust Conic Satisficing

In practical optimization problems, we typically model uncertainty as a random variable though its true probability distribution is unobservable to the decision maker. Historical data provides some information of this distribution that we can use to approximately quantify the risk of an evaluation function that depends on both our decision and the uncertainty. This empirical … Read more