|
所在平台: Coursera |
课程主页: https://www.coursera.org/learn/approximation-algorithms-part-2
课程评论：没有评论
课程名称：近似算法第二部分 课程概述：近似算法第二部分是近似算法第一部分的延续。在本课程中，您将学习线性规划对偶在某些近似算法设计中的应用，以及半正定规划在最大切割问题中的应用。通过参加这两部分课程，您将接触到理论计算机科学基础的一系列问题，以及强大的设计与分析技术。完成课程后，您将能够在面对新的组合优化问题时，识别其是否接近已知的基本问题，并能够设计线性规划松弛并使用随机舍入来尝试解决自己的问题。课程内容，尤其是家庭作业，侧重于理论性质，没有编程作业。 课程大纲： 第一部分：线性规划对偶 描述：此模块不研究任何特定的组合优化问题，而是介绍线性规划中的一个核心特征——对偶。 第二部分：斯坦纳森林和原始-对偶近似算法 描述：该模块利用线性规划对偶设计另一基本问题——斯坦纳森林问题的算法。 第三部分：设施选址和原始-对偶近似算法 描述：本模块继续讲授线性规划对偶的算法应用，将其应用于另一个基本问题——设施选址问题。 第四部分：最大切割和半正定规划 描述：我们介绍线性规划的一个推广——半正定规划。该模块利用半正定规划为另一个基本问题——最大切割问题设计了近似算法。
Part: 1
Title:Linear Programming Duality
Description:This module does not study any specific combinatorial optimization problem. Instead, it introduces a central feature of linear programming, duality.
Part: 2
Title:Steiner Forest and Primal-Dual Approximation Algorithms
Description:This module uses linear programming duality to design an algorithm for another basic problem, the Steiner forest problem.
Part: 3
Title:Facility Location and Primal-Dual Approximation Algorithms
Description:This module continues teaching algorithmic applications of linear programming duality by applying it to another basic problem, the facility location problem.
Part: 4
Title:Maximum Cut and Semi-Definite Programming
Description:We introduce a generalization of linear programming, semi-definite programming.This module uses semi-definite programming to design an approximation algorithm for another basic problem, the maximum cut problem.
Approximation algorithms, Part 2 This is the continuation of Approximation algorithms, Part 1. Here you will learn linear programming duality applied to the design of some approximation algorithms, and semidefinite programming applied to Maxcut. By taking the two parts of 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 second of a two-part course on Approximation Algorithms.
