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