近似算法，第一部分 如何高效地将物体装入最小数量的盒子中？如何才能将节点集群，从而以低成本将网络分成几个中心周围的组件？这些都是 NP 难组合优化问题的例子。要高效地解决这类问题很可能是不可能的，因此我们的目标是给出一个近似解，该解可以在多项式时间内计算，同时还能证明其相对于最优解的成本。

本课程假定您已学习过标准的本科算法课程，并特别强调可以使用线性规划来设计算法，线性规划是这一领域中最受欢迎和最成功的技术。通过学习本课程，您将接触到一系列计算机科学理论基础问题以及强大的设计和分析技术。学完这门课程后，您将能够在遇到新的组合优化问题时，识别出该问题是否接近已知的几个基本问题之一，并能够设计线性规划松弛和使用随机舍入来尝试解决自己的问题。课程内容，尤其是家庭作业是理论性的，没有任何编程作业。 这是 "逼近算法 "课程两部分中的第一部分。