Improved approximation algorithms for MAX n/2-DIRECTED-BISECTION and MAX n/2-DENSE-SUBGRAPH

CSpace

	Improved approximation algorithms for MAX n/2-DIRECTED-BISECTION and MAX n/2-DENSE-SUBGRAPH
	Xu, DC ; Han, JY ; Huang, ZH ; Zhang, LP
	2003-12-01
发表期刊	JOURNAL OF GLOBAL OPTIMIZATION
ISSN	0925-5001
卷号	27 期号:4 页码:399-410
摘要	We consider the MAX n/2-DIRECTED-BISECTION problem, i.e., partitioning the vertices of a directed graph into two blocks of equal cardinality so as to maximize the total weight of the edges in the directed cut. A polynomial approximation algorithm using a semidefinite-relaxation with 0.6458 performance guarantee is presented for the problem. The previous best-known results for approximating this problem are 0.5 using a linear programming relaxation, 0.6440 using a semidefinite relaxation. We also consider the MAX n/2-DENSE-SUBGRAPH problem, i.e., determine a block of half the number of vertices from a weighted undirected graph such that the sum of the edge weights, within the subgraph induced by the block, is maximized. We present an 0.6236 approximation of the problem as opposed to 0.6221 of Halperin and Zwick.
关键词	MAX n/2-DIRECTED-BISECTION MAX n/2-DENSE-SUBGRAPH polynomial-time approximation algorithm semidefinite programming
语种	英语
WOS研究方向	Operations Research & Management Science ; Mathematics
WOS类目	Operations Research & Management Science ; Mathematics, Applied
WOS记录号	WOS:000185797700003
出版者	KLUWER ACADEMIC PUBL
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/18323
专题	中国科学院数学与系统科学研究院
通讯作者	Xu, DC
作者单位	1.Chinese Acad Sci, Acad Math & Syst Sci, Inst Appl Math, Beijing 100080, Peoples R China 2.Tsing Hua Univ, Dept Math Sci, Beijing 100084, Peoples R China
推荐引用方式 GB/T 7714	Xu, DC,Han, JY,Huang, ZH,et al. Improved approximation algorithms for MAX n/2-DIRECTED-BISECTION and MAX n/2-DENSE-SUBGRAPH[J]. JOURNAL OF GLOBAL OPTIMIZATION,2003,27(4):399-410.
APA	Xu, DC,Han, JY,Huang, ZH,&Zhang, LP.(2003).Improved approximation algorithms for MAX n/2-DIRECTED-BISECTION and MAX n/2-DENSE-SUBGRAPH.JOURNAL OF GLOBAL OPTIMIZATION,27(4),399-410.
MLA	Xu, DC,et al."Improved approximation algorithms for MAX n/2-DIRECTED-BISECTION and MAX n/2-DENSE-SUBGRAPH".JOURNAL OF GLOBAL OPTIMIZATION 27.4(2003):399-410.