题目: An SDP Randomized Approximation Algorithm for Max Hypergraph Partition Problems

报告人: 张晓岩, 南京师范大学数学科学学院及数学研究所教授, 博士生导师

报告时间: 2017年12月14日下午16:15-17:00

地点: 知新楼B1032

摘要: 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.