An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance

We consider the design of semidefinite programming (SDP) based approximation algorithm for the problem Max Hypergraph Cut with Limited Unbalance (MHC-LU): Find a partition of the vertices of a weighted hypergraph H = (V,E) into two subsets V ₁, V ₂ with ||V ₂| ? |V ₁|| ? u for some given u and maximizing the total weight of the edges meeting both V ₁ and V ₂. The problem MHC-LU generalizes several other combinatorial optimization problems including Max Cut, Max Cut with Limited Unbalance (MC-LU), Max Set Splitting, Max Ek-Set Splitting and Max Hypergraph Bisection. By generalizing several earlier ideas, we present an SDP randomized approximation algorithm for MHC-LU with guaranteed worst-case performance ratios for various unbalance parameters τ = u/|V |. We also give the worst-case performance ratio of the SDP-algorithm for approximating MHC-LU regardless of the value of τ. Our strengthened SDP relaxation and rounding method improve a result of Ageev and Sviridenko (2000) on Max Hypergraph Bisection (MHC-LU with u = 0), and results of Andersson and Engebretsen (1999), Gaur and Krishnamurti (2001) and Zhang et al. (2004) on Max Set Splitting (MHC-LU with u = |V|). Furthermore, our new formula for the performance ratio by a tighter analysis compared with that in Galbiati and Maffioli (2007) is responsible for the improvement of a result of Galbiati and Maffioli (2007) on MC-LU for some range of τ.