Extremal Probability Bounds in Combinatorial Optimization

Understand

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 distributions with the given marginals.
• We analyze the complexity of computing the bounds assuming discrete marginals and identify instances when the bounds are computable in polynomial time.
• For compact 0/1 V-polytopes, we show that the tightest upper bound is weakly NP-hard to compute by providing a pseudopolynomial time algorithm.