0


在线算法的原始对偶方法

The Primal-Dual approach for Online Algorithms
课程网址: http://videolectures.net/algo2012_bansal_online_algorithms/  
主讲教师: Nikhil Bansal
开课单位: 视频讲座网
开课时间: 信息不详。欢迎您在右侧留言补充。
课程语种: 英语
中文简介:
在线算法处理输入数据随时间到达的设置,并且当前的决策必须由Algo-Rithm在不知道未来输入的情况下做出。在过去的几年中,由Buchbinder和Naor首创的在线原始对偶方法已经成为系统地设计和分析在线算法的一种非常强大和通用的方法。在本文中,我将概述该方法,并说明它如何统一和简化以前的各种结果。我还将描述这种方法在解决一些经典问题(如加权分页和随机K服务器问题)方面的最近成功。最后,我们还将看到该方法的一些最新扩展。
课程简介: Online algorithms deal with settings where the input data arrives over time and the current decision must be made by the algo- rithm without the knowledge of future input. In the last few years, the online primal-dual approach, pioneered by Buchbinder and Naor, has emerged as a very powerful and general method to systematically design and analyze online algorithms. In this talk, I will give an overview of the method and show how it uni es and simpli es various previous results. I will also describe the recent successes of this approach in addressing some classic problems such as weighted paging and the randomized k-server problem. Finally, we will also see some recent extensions of the method.
关 键 词: 在线算法处理设置; 网络对偶; 知识输入方法
课程来源: 信息不详。欢迎您在右侧留言补充。
入库时间: 2017-03-23
最后编审: 2017-03-23:sheny
阅读次数: 1