NP 完全问题与近似算法
识别 NP 完全问题（归约到已知问题）、然后选择：近似算法（顶点覆盖 2-近似、TSP 的 Christofides）、参数化算法、启发式与局部搜索、或精确的分支限界/SAT 求解器。本章是理论（第十卷）与实践之间的桥。
- NP 难不等于不能解，等于没有已知的通用多项式算法
- 现代 SAT/ILP 求解器能解很多”理论上难”的实例
- 近似比是可证明的质量保证
识别 NP 完全问题（归约到已知问题）、然后选择：近似算法（顶点覆盖 2-近似、TSP 的 Christofides）、参数化算法、启发式与局部搜索、或精确的分支限界/SAT 求解器。本章是理论（第十卷）与实践之间的桥。