Improved approximation algorithms for MAX n/2-DIRECTED-BISECTION and MAX n/2-DENSE-SUBGRAPH
文献类型：期刊论文
| 作者 | Xu, DC; Han, JY; Huang, ZH; Zhang, LP |
| 刊名 | JOURNAL OF GLOBAL OPTIMIZATION
 |
| 出版日期 | 2003-12-01 |
| 卷号 | 27期号:4页码:399-410 |
| 关键词 | MAX n/2-DIRECTED-BISECTION MAX n/2-DENSE-SUBGRAPH polynomial-time approximation algorithm semidefinite programming |
| ISSN号 | 0925-5001 |
| 英文摘要 | 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. |
| WOS研究方向 | Operations Research & Management Science ; Mathematics |
| 语种 | 英语 |
| WOS记录号 | WOS:000185797700003 |
| 出版者 | KLUWER ACADEMIC PUBL |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/18322]  |
| 专题 | 中国科学院数学与系统科学研究院 |
| 通讯作者 | 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. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。