题目: An SDP Randomized Approximation Algorithm for Max Hypergraph Partition Problems
报告人: 张晓岩, 南京师范大学数学科学学院及数学研究所教授, 博士生导师
摘要: We consider the design of semidefinite programming (SDP) based approximation algorithm for the problem Max Hypergraph Cut with Limited
Unbalance(MHC-LU). The problem MHC-LU generalizes several other classical 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 which also improve the worst case performance ratios of some classical problems.