现实世界中的许多算法问题无法使用传统的算法工具高效地解决,例如,因为这些问题是 NP-困难的。近似算法课程的目标是熟悉有效处理此类问题所需的重要算法概念和技术。当我们不需要某些问题的最优解,而只需要接近最优解的近似值时,这些技术就适用了。我们将了解如何有效地找到这种近似值。
了解顶级公司的员工如何掌握热门技能

该课程共有4个模块
本模块将介绍研究近似算法的动机。我们将讨论什么是优化问题,以及启发式算法和近似算法之间的区别。最后,我们将介绍近似率的概念,它在近似算法的质量分析中起着核心作用。
涵盖的内容
1个视频1篇阅读材料1个作业
在本模块中,我们将研究负载均衡问题的各种近似算法。这个问题要求将一组给定的作业(每个作业都有一定的处理时间)分配到多台计算机上。目标是尽快完成所有作业。我们将利用上一讲中提到的 "rho-近似 "概念来分析计算出的解决方案的质量。在分析中,我们会发现最优解的下限在分析中起着至关重要的作用(或者,对于最大化问题:上限)。
涵盖的内容
3个视频1篇阅读材料1个作业1个编程作业
在本模块中,我们将介绍设计近似算法的 LP 松弛技术,并解释如何分析基于 LP 松弛的算法的近似率。我们将以(加权)顶点覆盖问题为例进行讲解。不过,在解释 LP 松弛技术之前,我们首先要给出非加权顶点覆盖问题的简单 2 近似算法。
涵盖的内容
6个视频2篇阅读材料1个作业
在本模块中,我们将介绍多项式时间逼近方案(PTAS)的概念,这是一种可以任意接近最优解的算法。我们将介绍设计 PTAS 的一般技术,并将其应用于著名的 Knapsack 问题。最后,我们将了解如何分析用通用技术设计的 PTAS。
涵盖的内容
6个视频2篇阅读材料1个作业1个编程作业
位教师

提供方
人们为什么选择 Coursera 来帮助自己实现职业发展

Felipe M.

Jennifer J.

Larry W.

Chaitanya A.
学生评论
- 5 stars
78.78%
- 4 stars
15.15%
- 3 stars
3.03%
- 2 stars
3.03%
- 1 star
0%
显示 3/33 个
已于 Oct 10, 2020审阅
Please try to include some more numeric example like load balancing problem in the vertex cover and rest topics
已于 Feb 24, 2021审阅
Very good course! A nice introduction to approximation algorithms.
从 计算机科学 浏览更多内容

École normale supérieure

University of Colorado Boulder

École normale supérieure





