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...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 V1, V2 with ｜｜V2｜ - ｜1/1 ｜｜ ≤ u for some given u and maximizing the total weight of the edges meeting both V1 and V2. 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 τ.展开更多
基金supported by National Natural Science Foundation of China(Grant Nos.11171160,11331003 and 11471003)the Priority Academic Program Development of Jiangsu Higher Education Institutions+2 种基金the Natural Science Foundation of the Jiangsu Higher Education Institutions of China(Grant No.13KJB1100188)Natural Science Foundation of Guangdong Province(Grant No.S2012040007521)Sienceand Technology Planning Project in Guangzhou(Grant No.2013J4100077)
文摘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 V1, V2 with ｜｜V2｜ - ｜1/1 ｜｜ ≤ u for some given u and maximizing the total weight of the edges meeting both V1 and V2. 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 τ.
