An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems
From MaRDI portal
Publication:2354294
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
Related Items
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.