KMS Of Academy of mathematics and systems sciences, CAS
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 | |
Source Publication | JOURNAL OF GLOBAL OPTIMIZATION |
ISSN | 0925-5001 |
Volume | 27Issue:4Pages:399-410 |
Abstract | 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. |
Keyword | MAX n/2-DIRECTED-BISECTION MAX n/2-DENSE-SUBGRAPH polynomial-time approximation algorithm semidefinite programming |
Language | 英语 |
WOS Research Area | Operations Research & Management Science ; Mathematics |
WOS Subject | Operations Research & Management Science ; Mathematics, Applied |
WOS ID | WOS:000185797700003 |
Publisher | KLUWER ACADEMIC PUBL |
Citation statistics | |
Document Type | 期刊论文 |
Identifier | http://ir.amss.ac.cn/handle/2S8OKBNM/18323 |
Collection | 中国科学院数学与系统科学研究院 |
Corresponding Author | Xu, DC |
Affiliation | 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 |
Recommended Citation 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. |
Files in This Item: | ||||||
There are no files associated with this item. |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment