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

作　　者：XU BaoGang YU XingXing ZHANG XiaoYan ZHANG Zan-Bo 

机构地区：[1]School of Mathematical Sciences and Institute of Mathematics, Nanjing Normal University [2]School of Mathematics, Georgia Institute of Technology [3]Faculty of Electrical Engineering, Mathematics and Computer Science, University of Twente [4]Department of Computer Engineering, Guangdong Industry Technical College

出　　处：《Science China Mathematics》2014年第12期2437-2462,共26页中国科学：数学（英文版）

基　　金：supported by National Natural Science Foundation of China(Grant Nos.11171160,11331003 and 11471003);the Priority Academic Program Development of Jiangsu Higher Education Institutions;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 τ.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|- |V1‖ 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 τ.

关 键 词：max hypergraph cut with limited unbalance approximation algorithm performance ratio semidefinite programming relaxation 

分 类 号：O157.5[理学—数学]