期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

关于图划分问题的改进的近似算法 被引量：4

IMPROVED APPROXIMATION ALGORITHM FOR GRAPH PARTITION PROBLEM
原文传递
导出
摘要 本文考虑NP-难的极大图划分(MAX-GP)问题.我们给出应用半定规划(SDP) 松弛的一个一般方法,并且给出包括极大方向割,稠密子图,极大顶点覆盖,极大割,和极大反割在内的图划分问题的改进的近似比. In this paper, we consider maximum graph partition problem which is NP-hard. We propose a general method to design the approximation algorithm using semidefinite programming （SDP）. Improved approximation ratios for max dicut, dense-subgraph, max vertex-cover, max cut, max uncut are listed at several tables.
作者 徐大川 韩继业 杜东雷
机构地区 北京工业大学数理学院 中国科学院数学与系统科学研究院应用数学研究所 新布伦兹维克大学管理系
出处 《应用数学学报》 CSCD 北大核心 2005年第4期587-597,共11页 Acta Mathematicae Applicatae Sinica
基金 北京工业大学数理基金博士科研启动基金国家自然科学基金(10401038 10171108 10271002)NSERC 基金(10004901)资助项目.
关键词 图划分问题 近似算法 半定规划 Graph partition problem approximation algorithm semidefinite programming
分类号 O221.2 [理学—运筹学与控制论]
  • 相关文献

参考文献14

  • 1Papadimitriou C H, Yannakakis M. Optimization, Approximation, and Complexity Classes. J.Comput. Syst. Sci, 1991, 43:425-440.
  • 2Goemans M X, Williamson D P. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems using Semidefinite Programming. Journal of the ACM, 1995, 42:1115-1145.
  • 3Feige U, Goemans M X. Approximating the Value of Two Prover Proof Systems, with Applications to MAX 2SAT and MAX DICUT. In: Proceedings of the 3nd Israel Symposium on Theory and Computing Systems. Tel Aviv, Israel, 1995, 182-189.
  • 4Ageev A, Hassin R, Sviridenko M. A 0.5-approximation Algorithm for the Max Dicut with Given Sizes of Parts. SIAM J. Discrete Math, 2001, 14:246-255.
  • 5Halperin E, Zwick U. A Unified Framework for Obtaining Improved Approximation Algorithms for Maximum Graph Bisection Problems. Random Structures and Algorithms, 2002, 20:382-402.
  • 6Xu D, Han J, Huang Z, Zhang L. Improved Approximation Algorithms for Max n/2-directed-bisectionand Max n/2-dense-subgraph. Journal of Global Optimization, 2003, 27:399-410.
  • 7Han Q, Ye Y, Zhang J. An Improved Rounding Method and Semidefinite Programming Relaxation for Graph Partition. Mathematical Programming, 2002, 92:509-535.
  • 8Ye Y, Zhang J. Approximation of Dense-n/2-Subgraph and the Complement of Min-Bisection. Journal of Global Optimization, 2003, 25:55-73.
  • 9Ye Y. A 0.699-approximation Algorithm for Max-Bisection. Mathematical Programming, 2001, 90:101-111.
  • 10Feige U, Langberg M. The RPR2 Rounding Technique for Semidefinite Programs. Proceedings of the 28th Int. Coll. on Automata, Languages and Programming, Crete, Greece, 2001, 213-2204.

同被引文献29

  • 1林皎,陈文光,栗强,郑纬民,张益民.基于图划分的全基因组并行拼接算法[J].计算机研究与发展,2006,43(8):1323-1329. 被引量：5
  • 2Garg N, Vazirani V, Yannakakis M. Primal-dual approximation algorithm for integral flow and multicut in trees [J]. Algorithmica, 1997, 18(1): 3-20
  • 3Levin A, Segev D. Partial multicuts in trees[C] //Proc of the 3rd Workshop on Approximation and Online Algorithms (WAOA). Berlin: Springer, 2005:320-333
  • 4Jain K, Mahdian M, Markaksi E, et al. Greedy facility location algorithms analyzed using dual fitting with factorrevealing LP [J]. Journal of the ACM, 2003, 50(6): 795- 824
  • 5Golovin D, Nagarajan V, Singh M. Approximating the kmulticut problem [C]//Proc of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA). New York: ACM Press, 2006:621-630
  • 6Jain K, Vazirani V. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation[J]. Journal of the ACM, 2001, 48(2) : 274-296
  • 7Chudak F, Roughgarden T, Williamson D. Approximate k- MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation [J]. Mathematical Programming: Series A, 2004, 100(2): 411-421
  • 8Garg N, Vazirani V, Yannakakis M. Approximate max-flow min-(multi) cut theorems and their applications [J]. SIAM Journal on Computing, 1996, 25(2):235-251
  • 9Avidor A, Langberg M. The multi-multiway cut problem[C]//Proc of the 9th Scandinavian Workshop on Algorithm Theory (SWAT). Berlin: Springer, 2004:273-284
  • 10Agrawal A, Klein P, Ravi R. When trees collide: An approximation algorithm for the generalized Steiner problem on networks [J]. SIAM Journal of Computing, 1995, 24 (3) : 440-456

引证文献4

二级引证文献7

应用数学学报
2005年 第4期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部