课程概况
近似算法，第一部分
如何有效地将物品装入最少数量的盒子？您是否可以将节点集中在一起以便将网络廉价地分成几个中心的组件？这些是NP难组合优化问题的例子。很可能无法有效地解决这些问题，因此我们的目标是给出一个可以在多项式时间内计算的近似解，并且同时对其相对于最优的成本具有可证实的保证。
本课程需要已学过本科算法课程，尤其要求会使用线性编程设计的算法这一该领域最受欢迎和最成功的技术。通过本课程，您将接触到理论计算机科学基础上的一系列问题，以及强大的设计和分析技术。完成后，当遇到新的组合优化问题时，您将能够识别它是否接近一些已知的基本问题，并且能够设计线性编程松弛并使用随机舍入来尝试解决自己的问题。课程内容和课后作业具有理论性质，没有任何编程任务。
这是关于近似算法的两部分课程中的第一部分。
课程大纲
WEEK 1
Vertex cover and Linear Programming
We introduce the course topic by a typical example of a basic problem, called Vertex Cover, for which we will design and analyze a state-of-the-art approximation algorithm using two basic techniques, called Linear Programming Relaxation and Rounding. It is a s... 更多
WEEK 2
Knapsack and Rounding
This module shows the power of rounding by using it to design a near-optimal solution to another basic problem: the Knapsack problem.
WEEK 3
Bin Packing, Linear Programming and Rounding
This module shows the sophistication of rounding by using a clever variant for another basic problem: bin packing. (This is a more advanced module.)
WEEK 4
Set Cover and Randomized Rounding
This module introduces a simple and powerful variant of rounding, based on probability: randomized rounding. Its power is applied to another basic problem, the Set Cover problem.
WEEK 5
Multiway Cut and Randomized Rounding
This module deepens the understanding of randomized rounding by developing a sophisticated variant and applying it to another basic problem, the Multiway Cut problem. (This is a more advanced module.)
