DMMP Seminar

Xiaoyan Zhang — An SDP Approximation Algorithm for Max Hypergraph Cut with Limited Unbalance

Time: Thursday, December 16, 2010
Location: Room 101, Citadel

We consider the design of semidefinite programming 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 V1, V2 with ||V2|-|V1|| = u for some given u and maximizing the total weight of the edges meeting both V1 and V2. If all edges of H have size 2, then MHC-LU becomes the problem Max Cut with Limited Unbalance (MC-LU). When u = |V| and all edges have size 2, MHC-LU is the well-known Max Cut problem; when u = 0 and all edges have size 2, MHC-LU becomes the Max Bisection problem; and when u = |E|, MHC-LU is the Hypergraph Cut problem (also known as Max Set Splitting problem) and if, in addition, all edges are of size k ≥ 2 we have the Max Ek-Set Splitting problem. Although the aforementioned special cases of MHC-LU have been studied extensively, to the best of our knowledge the problem has not been studied in its most general form. We give a randomized approximation algorithm for MHC-LU, which extends earlier ideas (for special cases) of Galbiati and Maffioli (2007), Halperin and Zwick (2002), Andersson and Engebretsen (1998), Zhang et al. (2004) and Han et al. (2002). Our introduction of an additional constraint and tighter analysis allow us to improve a result of Galbiati and Maffioli (2007) on MC-LU, a result of Halperin and Zwick (2002) on Max Bisection, a result of Ageev and Sviridenko (2000) on Max Hypergraph Cut with u = 0, and a result of Zhang et al. (2004) on Max Set Splitting. We also obtain the same result of Zwick (1999) on Max E3-Set Splitting.