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

DOI10.1007/s10878-013-9673-1zbMath1327.90183OpenAlexW2086871104MaRDI QIDQ2354294

Chen-Chen Wu, Da-Chuan Xu, Dong-lei Du

Publication date: 10 July 2015

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-013-9673-1

zbMATH Keywords

approximation algorithmroundingsemidefinite programming hierarchiesgraph bisection problems

Mathematics Subject Classification ID

Semidefinite programming (90C22) Combinatorial optimization (90C27)

Related Items

An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding

Cites Work

• Unnamed Item
• Unnamed Item
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Improved approximation algorithms for MAX \(\frac{n}2\)-DIRECTED-BISECTION and MAX \(\frac{n}2\)-DENSE-SUBGRAPH
• An improved rounding method and semidefinite programming relaxation for graph partition
• Better approximation algorithms for influence maximization in online social networks
• An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
• An Improved Semidefinite Programming Hierarchies Rounding Approximation Algorithm for Maximum Graph Bisection Problems
• The RPR2 rounding technique for semidefinite programs
• Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
• A .699-approximation algorithm for Max-Bisection.