摘要
我们提出了一种承诺下的可恢复鲁棒优化模型。针对一个组合优化问题及其可能失效的元素的不确定性，我们要求一个鲁棒解，在失效元素被揭示后，可以以有限的方式进行增强。然而，我们承诺保留初始解中的非失效元素。我们解决了多种经典多项式时间可解组合优化问题的鲁棒对偶体的计算复杂性。
我们证明，对于加权的矩阵独立集问题，名义问题的最优解也是其鲁棒对偶体的最优解。实际上，矩阵是唯一具有此强性质的结构。其他问题的鲁棒对偶体，如匹配问题和稳定集问题，即使在二分图中也是 NP-hard。然而，我们为二分图中的无权稳定集问题和区间图中的加权稳定集问题（也称为区间调度问题）建立了多项式时间算法。
博主点评： 此研究为处理组合优化问题中的不确定性提供了新的视角，尤其是在承诺保留部分解的情况下，展示了鲁棒优化在实际应用中的潜力。该结果不仅丰富了理论框架，也为算法设计提供了新的思路。