An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance |
| |
Authors: | BaoGang Xu XingXing Yu XiaoYan Zhang Zan-Bo Zhang |
| |
Affiliation: | 1. School of Mathematical Science & Institute of Mathematics, Nanjing Normal University, Nanjing, 210023, China 2. School of Mathematics, Georgia Institute of Technology, Atlanta, GA, 30332, USA 3. Faculty of Electrical Engineering, Mathematics and Computer Science, University of Twente, Enschede, 7500, The Netherlands 4. Department of Computer Engineering, Guangdong Industry Technical College, Guangzhou, 510300, China
|
| |
Abstract: | 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 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. 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 τ. |
| |
Keywords: | max hypergraph cut with limited unbalance approximation algorithm performance ratio semidefinite programming relaxation |
本文献已被 CNKI SpringerLink 等数据库收录! |
|