图 书 馆
随机参数化算法的技术Randomized techniques for parameterized algorithms |
|
| 课程网址: | http://videolectures.net/algo2012_marx_parameterized_algorithms/ |
| 主讲教师: | Dániel Marx |
| 开课单位: | 匈牙利科学院 |
| 开课时间: | 信息不详。欢迎您在右侧留言补充。 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | Since the introduction of the Color Coding technique in 1994 by Alon, Yuster, and Zwick, randomization has been part of the toolkit for proving fixed-parameter tractability results. It seems that randomization is very well suited to parameterized algorithms: if the task is to find a solution of size k and only those random choices need to be correct that are directly related to the solution, then typically we can bound the error probability by a function of k. The talk will overview through various concrete examples how randomization appears in fixed-parameter tractability results. We argue that in many cases randomization appears in form of a reduction: it allows us to reduce the problem we are trying to solve to an easier and more structured problem. |
| 关 键 词: | 随机参数化; 算法; 技术 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2019-10-30：cwx |
| 阅读次数: | 34 |