图 书 馆
网络连接优化：基本限制和有效算法Network Connectivity Optimization: Fundamental Limits and Effective Algorithms |
|
| 课程网址: | http://videolectures.net/kdd2018_chen_network_connectivity_optimi... |
| 主讲教师: | Chen Chen |
| 开课单位: | 亚利桑那州立大学计算机科学与工程系 |
| 开课时间: | 2018-11-23 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | Network connectivity optimization, which aims to manipulate network connectivity by changing its underlying topology, is a fundamental task behind a wealth of high-impact data mining applications, ranging from immunization, critical infrastructure construction, social collaboration mining, bioinformatics analysis, to intelligent transportation system design. To tackle its exponential computation complexity, greedy algorithms have been extensively used for network connectivity optimization by exploiting its diminishing returns property. Despite the empirical success, two key challenges largely remain open. First, on the theoretic side, the hardness, as well as the approximability of the general network connectivity optimization problem are still nascent except for a few special instances. Second, on the algorithmic side, current algorithms are often hard to balance between the optimization quality and the computational efficiency. In this paper, we systematically address these two challenges for the network connectivity optimization problem. First, we reveal some fundamental limits by proving that, for a wide range of network connectivity optimization problems, (1) they are NP-hard and (2) (1 − 1/e) is the optimal approximation ratio for any polynomial algorithms. Second, we propose an effective, scalable and general algorithm (CONTAIN) to carefully balance the optimization quality and the computational efficiency. |
| 关 键 词: | 网络连接优化; 基本限制和有效算法; 可扩展的通用算法; 利用其递减收益特性 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2023-03-23：cyh |
| 最后编审: | 2023-03-27：cyh |
| 阅读次数: | 26 |