Well-Solved Problems
这部分介绍一些已经解决得很好的组合优化问题, 在此之前, 需要先定义什么叫做"解决得很好".
对于给定的组合优化问题
在判断一个问题是否有高效的算法的时候, 通常会同时用到下面的四个性质:
- efficient optimization性质: 对于给定的组合优化问题族存在高效的(多项式)算法.
- 强对偶性质: 对于给定的问题族,
存在可以让我们得到可以快速验证最优条件的强对偶问题
, 这个验证解的最优条件是: 是原问题 的最优解当且仅当存在 使得 . - efficient separation性质: 存在与组合优化问题相伴的分离问题的高效算法.
- 精确凸包性质: 原文中有compact description of convex hull,
不知道是什么意思, 反正就是原则上可以将每个实例替换为线性规划问题
.
以上