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 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. On the other hand, the tightest lower bound is shown to be strongly NP-hard to compute for compact 0/1 V-polytopes by restricting our attention to Bernoulli random variables. For compact 0/1 H-polytopes, for the special case of PERT networks arising in project management, we show that the tightest upper bound is weakly NP-hard to compute by providing a pseudopolynomial time algorithm. The results in the paper complement existing results in the literature for computing the probability with independent random variables.