课程信息
100% 在线

100% 在线

立即开始,按照自己的计划学习。
可灵活调整截止日期

可灵活调整截止日期

根据您的日程表重置截止日期。
中级

中级

完成时间(小时)

完成时间大约为12 小时

建议:9 hours/week...
可选语言

英语(English)

字幕:英语(English)
100% 在线

100% 在线

立即开始,按照自己的计划学习。
可灵活调整截止日期

可灵活调整截止日期

根据您的日程表重置截止日期。
中级

中级

完成时间(小时)

完成时间大约为12 小时

建议:9 hours/week...
可选语言

英语(English)

字幕:英语(English)

教学大纲 - 您将从这门课程中学到什么

1
完成时间(小时)
完成时间为 1 小时

Introduction to Approximation algorithms

In the module the motivation for studying approximation algorithms will be given. We will discuss what optimization problems are, and what the difference between heuristics and approximation algorithms is. Finally, we will introduce the concept of approximation ratio, which plays a central role in the analysis of the quality of approximation algorithms....
Reading
1 个视频 (总计 13 分钟), 1 个阅读材料, 1 个测验
Reading1 个阅读材料
Course notes 1.130分钟
Quiz1 个练习
Introduction20分钟
2
完成时间(小时)
完成时间为 5 小时

The Load Balancing problem

In this module we will study various approximation algorithms for the load balancing problem. This problems asks to distribute a given set of jobs, each with a certain processing time, over a number of machine. The goal is to do this such that all jobs are finished as soon as possible. We will analyze the quality of the computed solutions computed using the concept of rho-approximation, which we saw in the previous lecture. In this analysis we will see that lower bounds on the optimal solution play a crucial role in the analysis (or, for maximization problems: upper bounds)....
Reading
3 个视频 (总计 45 分钟), 1 个阅读材料, 2 个测验
Video3 个视频
Analysis of the greedy-algorithm19分钟
The ordered scheduling algorithm14分钟
Reading1 个阅读材料
Course notes 1.245分钟
Quiz1 个练习
The load balancing problem25分钟
3
完成时间(小时)
完成时间为 3 小时

LP Relaxation

In this module we will introduce the technique of LP relaxation to design approximation algorithms, and explain how to analyze the approximation ratio of an algorithm based in LP relaxation. We will do this using the (weighted) Vertex Cover problem as an example. Before we explain the technique of LP relaxation, however, we first give a simple 2-approximation algorithm for the unweighted Vertex Cover problem. ...
Reading
6 个视频 (总计 69 分钟), 2 个阅读材料, 1 个测验
Video6 个视频
An approximation algorithm for vertex-cover11分钟
A brief introduction to linear programming12分钟
Weighted vertex-cover15分钟
LP relaxation for weighted vertex-cover7分钟
LP relaxation: Analyzing approximation ratio12分钟
Reading2 个阅读材料
Course notes 3.120分钟
Course notes 3.245分钟
Quiz1 个练习
LP Relaxation30分钟
4
完成时间(小时)
完成时间为 6 小时

Polynomial-time approximation schemes

In this module we will introduce the concept of Polynomial-Time Approximation Scheme (PTAS), which are algorithms that can get arbitrarily close to an optimal solution. We describe a general technique to design PTASs, and apply it to the famous Knapsack problem. Finally we will see how to analyze PTASs that are designed with the general technique....
Reading
6 个视频 (总计 62 分钟), 2 个阅读材料, 2 个测验
Video6 个视频
Knapsack Problem6分钟
A dynamic-programming algorithm for knapsack16分钟
A PTAS for knapsack12分钟
Analysis of the PTAS for knapsack: approximation ratio11分钟
Analysis of the PTAS for knapsack: running time8分钟
Reading2 个阅读材料
Course notes 4.145分钟
Course notes 4.245分钟
Quiz1 个练习
Polynomial-time approximation schemes45分钟

讲师

Avatar

Mark de Berg

Prof.dr.
Mathematics and Computer Science

关于 EIT 数字

EIT Digital is a pan-European education and research-based open innovation organization founded on excellence. Its mission is to foster digital technology innovation and entrepreneurial talent for economic growth and quality of life. By linking education, research and business, EIT Digital empowers digital top talents for the future. EIT Digital provides online "blended" Innovation and Entrepreneurship education to raise quality, increase diversity and availability of the top-level content provided by 20 reputable universities of technology around Europe. The universities all together deliver a unique blend of the best of technical excellence and entrepreneurial skills and mindset to digital engineers and entrepreneurs at all stages of their careers. The academic partners support Coursera’s bold vision to enable anyone, anywhere, to transform their lives by accessing the world’s best learning experience. This means that EIT Digital gradually shares parts of its entrepreneurial and academic education programmes to demonstrate its excellence and make it accessible to a much wider audience. EIT Digital’s online education portfolio can be used as part of blended education settings, in both Master and Doctorate programmes, and for professionals as a way to update their knowledge. EIT Digital offers an online programme in 'Internet of Things through Embedded Systems'. Achieving all certificates of the online courses and the specialization provides an opportunity to enroll in the on campus program and get a double degree. These are the courses in the online programme: ...

常见问题

  • 注册以便获得证书后,您将有权访问所有视频、测验和编程作业(如果适用)。只有在您的班次开课之后,才可以提交和审阅同学互评作业。如果您选择在不购买的情况下浏览课程,可能无法访问某些作业。

  • 您购买证书后,将有权访问所有课程材料,包括评分作业。完成课程后,您的电子课程证书将添加到您的成就页中,您可以通过该页打印您的课程证书或将其添加到您的领英档案中。如果您只想阅读和查看课程内容,可以免费旁听课程。

还有其他问题吗?请访问 学生帮助中心