稠密平分子图与表压缩问题的近似算法

CSpace

	稠密平分子图与表压缩问题的近似算法
	徐大川 1; 韩继业 2; 杜东雷 3
	2005
Source Publication	中国科学a辑数学
ISSN	1006-9232
Volume	035 Issue:007 Pages:745
Abstract	给出两个NP问题(稠密平分子图和表压缩)的改进的近似算法．基于半定规划(SDP)松弛和巧妙的舍入技巧，首先给出稠密平分子图问题(DSP)的0．5982．近似算法，表压缩问题(TCP)的0．5970．近似算法．然后，通过增加三角不等式得到更紧的SDP松弛，把前面的比值分别改进到0．6243和0．6708．针对TCP得到的结果改进了简单贪婪算法的0．5近似比，因此回答了Anderson提出的未解决问题．
Language	英语
Document Type	期刊论文
Identifier	http://ir.amss.ac.cn/handle/2S8OKBNM/44593
Collection	中国科学院数学与系统科学研究院
Affiliation	1.北京工业大学 2.中国科学院数学与系统科学研究院 3.Faculty of Administration,University of New Brunswick
Recommended Citation GB/T 7714	徐大川,韩继业,杜东雷. 稠密平分子图与表压缩问题的近似算法[J]. 中国科学a辑数学,2005,035(007):745.
APA	徐大川,韩继业,&杜东雷.(2005).稠密平分子图与表压缩问题的近似算法.中国科学a辑数学,035(007),745.
MLA	徐大川,et al."稠密平分子图与表压缩问题的近似算法".中国科学a辑数学 035.007(2005):745.

Files in This Item:
There are no files associated with this item.

Related Services

Bookmark

Google Scholar

Similar articles in Bing Scholar

Terms of Use

No data!

Social Bookmark/Share

All comments (0)

No comment.

The comment function is only available to registered usersLog In

If you have any objections to this item, please fill out the form below and the administrator will contact you as soon as possible.
Content:
Email：	*
Institution:
Verification Code:	Refresh

Any comments and suggestions are welcomed.
Title:	*
Content:
Email：	*
Verification Code:	Refresh

中国科学院数学与系统科学研究院机构知识库