Approximation Algorithms Part I

开始时间: 10/17/2020 持续时间: Unknown

所在平台: Coursera

课程类别: 其他类别

大学或机构: CourseraNew



Explore 1600+ online courses from top universities. Join Coursera today to learn data science, programming, business strategy, and more.


第一个写评论        关注课程


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.

近似算法第I部分:近似算法,第I部分 您如何有效地将对象包装到最少数量的箱子中?您如何对节点进行群集,以廉价地将网络划分为几个中心附近的组件?这些是NP难的组合优化问题的示例。很有可能不可能有效地解决这些问题,因此我们的目标是给出可以在多项式时间内计算的近似解,同时又可以相对于最优解提供可证明的成本保证。 本课程假定您具备标准的本科算法课程的知识,并且特别强调可以使用线性编程设计的算法,这是该领域一种最受欢迎且非常成功的技术。通过学习本课程,您将在理论计算机科学的基础上接触到一系列问题,并接触到强大的设计和分析技术。完成后,当面对新的组合优化问题时,您将能够识别它是否接近一些已知的基本问题,并且能够设计线性编程松弛并使用随机舍入来尝试解决您的问题。自己的问题。课程内容,尤其是家庭作业,具有理论性质,无需进行任何编程作业。 这是关于近似算法的两部分课程的第一部分。


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.





Approximation algorithms, Part I How efficiently can you pack objects into a minimum number of boxe