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

APPROXIMATION ALGORITHM FOR MAX-BISECTION PROBLEM WITH THE POSITIVE SEMIDEFINITE RELAXATION 被引量：3

APPROXIMATION ALGORITHM FOR MAX-BISECTION PROBLEM WITH THE POSITIVE SEMIDEFINITE RELAXATION
原文传递
导出
摘要 Using outward rotations, we obtain an approximation algorithm for Max-Bisection problem, i.e., partitioning the vertices of an undirected graph into two blocks of equal cardinality so as to maximize the weights of crossing edges. In many interesting cases, the algorithm performs better than the algorithms of Ye and of Halperin and Zwick. The main tool used to obtain this result is semidefinite programming. Using outward rotations, we obtain an approximation algorithm for Max-Bisection problem, i.e., partitioning the vertices of an undirected graph into two blocks of equal cardinality so as to maximize the weights of crossing edges. In many interesting cases, the algorithm performs better than the algorithms of Ye and of Halperin and Zwick. The main tool used to obtain this result is semidefinite programming.
作者 Da-chuan Xu Ji-ye Han(Institute of Applied Mathematics, Academy of Mathematics and System Sciences, Chinese Academyof Sciences, Beijing 100080, China)
出处 《Journal of Computational Mathematics》 SCIE CSCD 2003年第3期357-366,共10页 计算数学（英文）
基金 Research partly supported by Chinese NSF grant 19731001 and National 973 Information Technology and High-Performance Software Program of China with grant No.G1998030401.The first author gratefully acknowledges the support of K.C.Wong Education Foundat
关键词 Approximation algorithm Max-Bisection problem Semidefinite programming Approximation ratio. Approximation algorithm, Max-Bisection problem, Semidefinite programming, Approximation ratio.
分类号 O241.5 [理学—计算数学]
  • 相关文献

参考文献13

  • 1A. Frieze and M. Jerrum, Improved approximation algorithms for max k-cut and max bisection,in Proc. 4th IPCO Conference, pages 1-13, 1995.
  • 2U. Feige, Randomized rounding of semidefinite programs - variations on the MAX CUT example, Randomization, Approximation, and Combinatorial Optimization, Proceedings of Random-Approx'99, Lecture Notes in Computer Science 1671, Springer 1999, pp. 189-196.
  • 3U. Feige and M. X. Goemans, 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, pages 182-189, Tel Aviv, Israel, 1995.
  • 4U. Feige, M. Karpinski, and M. Langberg, A note on approximating MAX-BISECTION on regular graphs, Electronic Colloquium on Computational Complexity, Report No. 43, 2000.
  • 5U. Feige and M. Langberg, Approximation algorithms for maximization problems arising in graph partitioning, Journal of Algorithms, 41 (2001), 174-211.
  • 6M. X. Goemans and D. P. Williarnson, Improved approximation algorithms for Maximum Cut and Satisfiability problems using semidefinite programming, Journal of ACM, 42 (1995), 1115-1145.
  • 7E. Halperin and U. Zwick, Improved approximation algorithms for maximum graph bisection problems, Proc. of 8th IPCO, pages 210-225, 2001, To appear in Random Structures and Algo-rithms.
  • 8Q. Han, Y. Ye, H. Zhang, and J. Zhang, On approximation of Max-Vertex-Cover, European Journal of Operational Research, 143:2 (2002), 207-220.
  • 9Q. Han, Y. Ye, and J. Zhang, An improved rounding method and semidefinite programming relaxation for graph partition, Mathematical Programming, 92:3 (2002), 509-535.
  • 10Y. Nesterov, Semidefinite relaxation and nonconvex quadratic optimization, Optimization Methods and Software, 9 (1998), 141-160.

同被引文献26

  • 1Yinyu Ye,Jiawei Zhang.Approximation of Dense-n/2-Subgraph and the Complement of Min-Bisection[J].Journal of Global Optimization.2003(1)
  • 2Qiaoming Han,Yinyu Ye,Jiawei Zhang.An improved rounding method and semidefinite programming relaxation for graph partition[J].Mathematical Programming.2002(3)
  • 3Yinyu Ye.A .699-approximation algorithm for Max-Bisection[J].Mathematical Programming.2001(1)
  • 4Shuzhong Zhang.Quadratic maximization and semidefinite relaxation[J].Mathematical Programming.2000(3)
  • 5Goemans M X, Williamson D P. Improved approximation algorithms for maximum cut andsatisfiability problem using semidefinite programming [J]. Journal of the ACM, 1995,42: 1115-1145.
  • 6Hastad J. Some optimal inapproximability results [J]. Journal of the ACM, 2001, 48: 798-859.
  • 7Khot S, Kindler G, Mossel E, et al. Optimal inapproximability results for max-cut and other2-variable CSPs? [J]. Journal on Computing, SIAM, 2007, 37: 319-357.
  • 8Avidor A,Zwick U. Rounding two and three dimensional solutions of the SDP relaxation ofmax cut [C]//Proceedings of Approx and Random 2005,Berkeley: Springer, 2005,14-25.
  • 9Feige U. Randomized rounding of semidefinite programs-variations on the max cut example[C]//Proceedings of Random-Approx}99, Berkeley: Springer, 1999,189-196.
  • 10Feige U, Goemans M X. Approximating the value of two prover proof systems, with applicationsto MAX 2SAT and MAX l5lCUT [C] //Proceedings of the Third Israel Symposium Theory andComputing and Systems, Israel: IEEE} 1995, 182-189.

引证文献3

二级引证文献6

Journal of Computational Mathematics
2003年 第3期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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