An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems

详细信息    查看全文

• 作者：Chenchen Wu (1)
  Donglei Du (2)
  Dachuan Xu (1)
  
  1. Department of Applied Mathematics ; Beijing University of Technology ; 100 Pingleyuan ; Chaoyang District ; Beijing聽 ; 100124 ; People鈥檚 Republic of China
  2. Faculty of Business Administration ; University of New Brunswick ; Fredericton ; NB聽 ; E3B 9Y2 ; Canada
  
• 关键词：Semidefinite programming hierarchies ; Approximation algorithm ; Rounding ; Graph bisection problems
• 刊名：Journal of Combinatorial Optimization
• 出版年：2015
• 出版时间：January 2015
• 年：2015
• 卷：29
• 期：1
• 页码：53-66
• 全文大小：183 KB
• 参考文献：1. Austrin P, Benabbas S, Georgiou K (2013) Better balance by being biased: a \(0.8776\) -approximation for max bisection. In: Proceedings of SODA, pp 277鈥?94
  2. Bhaskara A, Charikar M, Vijayaraghavan A, Guruswami V, Zhou Y (2012) Polynomial integrality gaps for strong SDP relaxations of Densest \(k\) -subgraph. In: Proceeding of SODA, pp 388鈥?05
  3. Feige U, Langberg M (2006) The \(\text{ RPR }^2\) rounding technique for semidefinite programs. J Algor 60:1鈥?3 CrossRef
  4. Frieze AM, Jerrum M (1997) Improved approximation algorithms for MAX \(k\) -CUT and MAX BISECTION. Algorithmica 18:67鈥?1 CrossRef
  5. Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM 42:1115鈥?145 CrossRef
  6. Halperin E, Zwick U (2002) A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems. Random Struct Algor 20:382鈥?02 CrossRef
  7. Han Q, Ye Y, Zhang J (2002) An improved rounding method and semidefinite programming relaxation for graph partition. Math Program Ser B 92:509鈥?35 CrossRef
  8. Lasserre JB (2002) An explicit equivalent positive semidefinite program for nonlinear 0鈥? programs. SIAM J Optim 12:756鈥?69 CrossRef
  9. Raghavendra P, Tan N (2012) Approximating CSPs with global cardinality constraints using SDP hierarchies. In: Proceedings of SODA, pp 373鈥?87
  10. Wu C, Du D, Xu D (2013) An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems. In: Proceedings of COCOON, pp 304鈥?15
  11. Xu D, Han J, Huang Z, Zhang L (2003) Improved approximation algorithms for MAX \(n/2\) -DIRECTED-BISECTION and MAX \(n/2\) -DENSE-SUBGRAPH. J Global Optim 27:399鈥?10 CrossRef
  12. Ye Y (2001) A \(.699\) -approximation algorithm for Max-Bisection. Math Program 90:101鈥?11 CrossRef
  13. Zhu Y, Wu W, Bi Y, Wu L, Jiang Y, Xu W (2013) Better approximation algorithms for influence maximization in online social networks. J Comb Optim. doi:10.1007/s10878-013-9635-7
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886

文摘

We present a unified semidefinite programming hierarchies rounding approximation algorithm for a class of maximum graph bisection problems with improved approximation ratios. Under the above algorithmic framework, we show that the approximation ratios of Max- \(\frac{n}{2}\) -cut, Max- \(\frac{n}{2}\) -dense-subgraph, and Max- \(\frac{n}{2}\) -vertex-cover are equal to those of Max- \(\frac{n}{2}\) -uncut, Max- \(\frac{n}{2}\) -directed-cut, and Max- \(\frac{n}{2}\) -directed-uncut, respectively.