文献类型：期刊文章

作　　者：郭传好[1] 单而芳[1]

机构地区：[1]上海大学管理学院管理科学与工程系,上海200444

出　　处：《运筹与管理》

基　　金：国家自然科学基金资助项目(11501350)

年　　份：2015

卷　　号：24

期　　号：5

起止页码：144-150

语　　种：中文

收录情况：BDHX、BDHX2014、CSCD、CSCD2015_2016、CSSCI、CSSCI_E2014_2016、JST、NSSD、RCCSE、RWSKHX、ZGKJHX、核心刊

摘　　要：稠密k-子图问题是组合优化里面一类经典的优化问题,其在通常情况下是非凸且NP-难的。本文给出了求解该问题的一个新凸松弛方法-双非负松弛方法,并建立了问题的相应双非负松弛模型,而且证明了其在一定的条件下等价于一个新的半定松弛模型。最后,我们使用一些随机例子对这些模型进行了数值测试,测试的结果表明双非负松弛的计算效果要优于等价的半定松弛。

关 键 词：组合优化 双非负松弛  半定松弛  稠密k-子图  

分 类 号：O221.7]