| 稠密k-子图问题的双非负松弛 |
| |
| 引用本文： | 郭传好,单而芳. 稠密k-子图问题的双非负松弛[J]. 运筹与管理, 2015, 24(5): 144-150. DOI: 10.12005/orms.2015.0170 |
| |
| 作者姓名： | 郭传好 单而芳 |
| |
| 作者单位： | 上海大学管理学院管理科学与工程系,上海200444 |
| |
| 基金项目： | 国家自然科学基金资助项目(11501350) |
| |
| 摘 要： | 稠密k-子图问题是组合优化里面一类经典的优化问题,其在通常情况下是非凸且NP-难的。本文给出了求解该问题的一个新凸松弛方法-双非负松弛方法,并建立了问题的相应双非负松弛模型,而且证明了其在一定的条件下等价于一个新的半定松弛模型。最后,我们使用一些随机例子对这些模型进行了数值测试,测试的结果表明双非负松弛的计算效果要优于等价的半定松弛。
|
| 关 键 词： | 组合优化 双非负松弛 半定松弛 稠密k-子图 |
| 收稿时间： | 2014-01-23 |
Doubly Nonnegative Relaxation for Densest k-subgraph Problem |
| |
| GUO Chuan-hao,SHAN Er-fang. Doubly Nonnegative Relaxation for Densest k-subgraph Problem[J]. Operations Research and Management Science, 2015, 24(5): 144-150. DOI: 10.12005/orms.2015.0170 |
| |
| Authors: | GUO Chuan-hao SHAN Er-fang |
| |
| Affiliation: | Department of Management Science and Engineering, School of Management, Shanghai University, Shanghai 200444, China |
| |
| Abstract: | Densest k-subgraph problem is a classical problem of combinatorial optimization, which is nonconvex and NP-hard in general. In this paper, we propose a new convex relaxation method, i.e., doubly non-negative relaxation method, for solving this problem, and establish the corresponding doubly nonnegative relaxation model for the problem. Moreover, we prove that the doubly nonnegative relaxation model is equivalent to a new semidefinite relaxation model under some conditions. Finally, some random examples are tested by these relaxation models. The numerical results show that the doubly non-negative relaxation is more promising than the corresponding semidefinite relaxation.
|
| |
| Keywords: | combinatorial optimization doubly nonnegative relaxation semidefinite relaxation densest k-subgraph |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《运筹与管理》浏览原始摘要信息 |
|
点击此处可从《运筹与管理》下载全文 |
|
