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

	Approximation algorithm for Max-Bisection problem with the positive semidefinite relaxation
	Xu, DC; Han, JY
刊名	JOURNAL OF COMPUTATIONAL MATHEMATICS
	2003-05-01
卷号	21 期号:3 页码:357-366
关键词	approximation algorithm Max-Bisection problem semidefinite programming approximation ratio
ISSN号	0254-9409
英文摘要	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.
WOS研究方向	Mathematics
语种	英语
出版者	VSP BV
WOS记录号	WOS:000183218200011
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/18028]
专题	中国科学院数学与系统科学研究院
作者单位	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.