首页 | 本学科首页   官方微博 | 高级检索  
     

稠密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 等数据库收录!
点击此处可从《运筹与管理》浏览原始摘要信息
点击此处可从《运筹与管理》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号