课程主页: https://www.coursera.org/learn/approximation-algorithms-part-2
近似算法第二部分课程是对第一部分的延续，专注于线性规划对偶性和半定规划在近似算法设计中的应用。这门课程将深入探讨理论计算机科学中的一些基础问题，以及强大的设计和分析技术。在完成这两个部分课程后，您将能够识别和分析新的优化问题。 课程的几个重要模块包括：
1. **线性规划对偶性** – 本模块不研究任何特定的组合优化问题，而是介绍了线性规划的一个核心特征：对偶性。这是理解后续内容的基础。
2. **Steiner森林与原始-对偶近似算法** – 在这一模块中，学员将利用线性规划对偶性设计一个算法来解决Steiner森林问题，这是一个基本的网络优化问题。
3. **设施选址与原始-对偶近似算法** – 本模块继续介绍线性规划对偶性的算法应用，特别是设施选址问题。这是日常生活中常见的优化问题，涉及如何最有效地布局服务设施。
4. **最大割与半定规划** – 这一模块引入了线性规划的推广——半定规划，并使用它设计出最大割问题的近似算法。
通过学习本课程，学生不仅能够掌握相关的算法设计技巧，还能够应用于更复杂的问题中，对于即将面临的各种新问题有更深的理解与应对能力。总的来说，近似算法第二部分是一门理论深度与实际应用价值兼具的课程，非常适合希望深入计算机科学领域的学习者。
课程主页: https://www.coursera.org/learn/approximation-algorithms-part-2