Approximation algorithm for Max-Bisection problem with the positive semidefinite relaxation

CSpace

	Approximation algorithm for Max-Bisection problem with the positive semidefinite relaxation
	Xu, DC; Han, JY
	2003-05-01
发表期刊	JOURNAL OF COMPUTATIONAL MATHEMATICS
ISSN	0254-9409
卷号	21 期号:3 页码:357-366
摘要	Using outward rotations, we obtain an approximation algorithm for Max-Bisection problem, i.e., partitioning the vertices of an undirected graph into two blocks of equal cardinality so as to maximize the weights of crossing edges. In many interesting cases, the algorithm performs better than the algorithms of Ye and of Halperin and Zwick. The main tool used to obtain this result is semidefinite programming.
关键词	approximation algorithm Max-Bisection problem semidefinite programming approximation ratio
语种	英语
WOS研究方向	Mathematics
WOS类目	Mathematics, Applied ; Mathematics
WOS记录号	WOS:000183218200011
出版者	VSP BV
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/18029
专题	中国科学院数学与系统科学研究院
作者单位	Chinese Acad Sci, Acad Math & Syst Sci, Inst Appl Math, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Xu, DC,Han, JY. Approximation algorithm for Max-Bisection problem with the positive semidefinite relaxation[J]. JOURNAL OF COMPUTATIONAL MATHEMATICS,2003,21(3):357-366.
APA	Xu, DC,&Han, JY.(2003).Approximation algorithm for Max-Bisection problem with the positive semidefinite relaxation.JOURNAL OF COMPUTATIONAL MATHEMATICS,21(3),357-366.
MLA	Xu, DC,et al."Approximation algorithm for Max-Bisection problem with the positive semidefinite relaxation".JOURNAL OF COMPUTATIONAL MATHEMATICS 21.3(2003):357-366.