|
所在平台: Coursera |
课程主页: https://www.coursera.org/learn/approximation-algorithms-part-1
课程评论：没有评论
课程名称：近似算法第一部分 课程概述：在本课程中，我们将探讨近似算法，特别是如何以最有效的方式将对象放入最少数量的箱子中，以及如何将节点聚类，以便便宜地将网络分离成围绕几个中心的组件。这些都是NP难度的组合优化问题，而有效解决这些问题几乎是不可能的，因此我们的目标是提供可以在多项式时间内计算的近似解决方案，同时保证其成本相对于最优解的有效性。 本课程假设学员具备标准本科算法课程的知识，尤其强调使用线性规划所设计的算法，这一技术在该领域中极为成功且强大。通过学习本课程，学员将接触到理论计算机科学基础中的一系列问题，并掌握强大的设计与分析技巧。完成课程后，学员将能够识别新遇到的组合优化问题是否接近于已知的一些基本问题，并能设计线性规划松弛，并利用随机舍入尝试解决自己的问题。本课程内容以及作业都是理论性质的，不涉及任何编程任务。 这是近似算法的两部分课程中的第一部分。 课程大纲： 1. **顶点覆盖与线性规划** 在这一模块中，我们通过一个典型的基本问题——顶点覆盖，来引入课程主题。我们将设计和分析一种最先进的近似算法，使用线性规划松弛和舍入等基本技术。这是强大技术的一个简单应用。 2. **背包问题与舍入** 此模块展示了舍入的力量，应用于设计另一个基本问题：背包问题的近似解决方案。 3. **装箱问题、线性规划和舍入** 本模块通过使用聪明的变体，展示了舍入的复杂性，应用于另一个基本问题：装箱问题（这是一个更高级的模块）。 4. **集合覆盖与随机舍入** 这一模块介绍了一种简单而强大的舍入变体，基于概率的随机舍入。其力量应用于另一个基本问题：集合覆盖问题。 5. **多路切割与随机舍入** 本模块深入理解随机舍入，通过发展一种复杂的变体，并将其应用于另一个基本问题：多路切割问题（这是一个更高级的模块）。
Name:Vertex cover and Linear Programming
Description: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 simple, elementary application of powerful techniques.
Name:Knapsack and Rounding
Description:This module shows the power of rounding by using it to design a near-optimal solution to another basic problem: the Knapsack problem.
Name:Bin Packing, Linear Programming and Rounding
Description:This module shows the sophistication of rounding by using a clever variant for another basic problem: bin packing. (This is a more advanced module.)
Name:Set Cover and Randomized Rounding
Description: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.
Name:Multiway Cut and Randomized Rounding
Description: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.)
Approximation algorithms, Part I How efficiently can you pack objects into a minimum number of boxes? How well can you cluster nodes so as to cheaply separate a network into components around a few centers? These are examples of NP-hard combinatorial optimization problems. It is most likely impossible to solve such problems efficiently, so our aim is to give an approximate solution that can be computed in polynomial time and that at the same time has provable guarantees on its cost relative to the optimum. This course assumes knowledge of a standard undergraduate Algorithms course, and particularly emphasizes algorithms that can be designed using linear programming, a favorite and amazingly successful technique in this area. By taking this course, you will be exposed to a range of problems at the foundations of theoretical computer science, and to powerful design and analysis techniques. Upon completion, you will be able to recognize, when faced with a new combinatorial optimization problem, whether it is close to one of a few known basic problems, and will be able to design linear programming relaxations and use randomized rounding to attempt to solve your own problem. The course content and in particular the homework is of a theoretical nature without any programming assignments. This is the first of a two-part course on Approximation Algorithms.
