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

Approximation Algorithm for MAX DICUT with Given Sizes of Parts

Approximation Algorithm for MAX DICUT with Given Sizes of Parts
原文传递
导出
摘要 Abstract Given a directed graph G and an edge weight function w : A(G) M R^+ the maximum directed cut problem (MAX DICUT) is that of finding a directed cut '(S) with maximum total weight. We consider a version of MAX DICUT -- MAX DICUT with given sizes of parts or MAX DICUT WITH GSP -- whose instance is that of MAX DICUT plus a positive integer k, and it is required to find a directed cut '(S) having maximum weight over all cuts '(S) with |S|=k. We present an approximation algorithm for this problem which is based on semidefinite programming (SDP) relaxation. The algorithm achieves the presently best performance guarantee for a range of k. Abstract Given a directed graph G and an edge weight function w : A(G) M R^+ the maximum directed cut problem (MAX DICUT) is that of finding a directed cut '(S) with maximum total weight. We consider a version of MAX DICUT -- MAX DICUT with given sizes of parts or MAX DICUT WITH GSP -- whose instance is that of MAX DICUT plus a positive integer k, and it is required to find a directed cut '(S) having maximum weight over all cuts '(S) with |S|=k. We present an approximation algorithm for this problem which is based on semidefinite programming (SDP) relaxation. The algorithm achieves the presently best performance guarantee for a range of k.
作者 DachuanXu GuanghuiLiu
机构地区 InstituteofAppliedMathematics WHQKB
出处 《Acta Mathematicae Applicatae Sinica》 SCIE CSCD 2003年第2期289-296,共8页 应用数学学报（英文版）
基金 Supported by K. C. Wong Education Foundation of Hong Kong,Chinese NSF (Grant No.19731001) National 973 Information Technology and High-Performance Software Program of China (Grant No.G1998030401)
关键词 Keywords MAX DICUT polynomial-time approximation algorithm semidefinite programming Keywords MAX DICUT, polynomial-time approximation algorithm, semidefinite programming
分类号 O157.5 [理学—基础数学]
  • 相关文献

参考文献16

  • 1Ye, Y, Zhang, J.Approximation of dense-n/2-subgraph and the complement of Min-Bisection. Journal of Global Optimization, 25(1): 55-73 (2003).
  • 2Zwick, U. Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems. In: Proceedings of the 30th Symposium on Theory of Computation (STOC), 551-560, 1999.
  • 3Ageev, A., Hassin, R., Sviridenko, M. An 0.5-approximation algorithm for the max dicut with given sizes of parts. SIAM Journal on Discrete Mathematics, 14(2): 246-255 (2001).
  • 4Bertsimas, D., Ye, Y. Semidefinite relaxations, multivariate normal distributions, and order statistics. In:Handbook of Combinatorial Optimization, Vol.3, Du, D.Z. and Pardalos, P.M. eds., Kluwer Academic Publishers, Norwell, MA, 1-19, 1998.
  • 5Feige, 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, 182-189, 1995.
  • 6Feige, U., Langberg, M. Approximation algorithms for maximization problems arising in graph partitioning.Journal of Algorithms, 41:174-211 (2001).
  • 7Frieze, A., Jerrum, M. Improved approximation algorithms for max κ-cut and max bisection. In: Proc.4th IPCO Conference, 1-13, 1995.
  • 8Goemans, M.X., Williamson, D.P. Improved approximation algorithms for Maximum Cut and Satisfiability problems using semidefinite programming. Journal of ACM, 42:1115-1145 (1995).
  • 9Halperin, E., Zwick, U. Improved approximation algorithms for maximum graph bisection problems. Proc.of 8th IPCO, 210-225, (2001) (to appear in Random Structures and Algorithms).
  • 10Han,Q.,Ye,Y.,Zhang,H.,Zhang,J. On approximation of Max-Vertex-Cover. European Journal of Operational Research, 143(2): 207-220 (2002).
Acta Mathematicae Applicatae Sinica
2003年 第2期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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