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 (V1, V2) 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.