An improved SDP rounding approximation algorithm for the max hypergraph bisection

We explore the well-known max hypergraph bisection problem, which is widely used in fields such as very large-scale integration layout design, network planning, biological networks and quantum computing. Given a hypergraph H = (V, E, ω) with a non-negative weight function ω: E → ℝ_⩾0, the goal is to find a balanced partition (V₁, V₂) while maximizing the total weight of hyperedges crossing different vertex subsets. For this purpose, we relax the max hypergraph bisection problem using the Lasserre hierarchy semidefinite programming. Then we design a new approximation algorithm combining random hyperplane and perturbation, and analyze the approximation factor via reducing dimensions and using interval arithmetic. Finally, we prove that if all hyperedges contain at least 3 vertices, the approximation factor is 0.7728; otherwise, the approximation factor is 0.6818. To the best of our knowledge, these results are the current best ones.