## 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 *V*_{1}, *V*_{2} with ||*V*_{2}|-|*V*_{1}|| = *u* for
some given *u* and maximizing
the total weight of the edges meeting both *V*_{1} and *V*_{2}. 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
E*k*-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.