论文部分内容阅读
最大割问题(Max-Cut Problem)是组合优化中经典的NP-困难问题.对于最大割问题，很多算法是基于半定规划(SDP)松弛的技巧研究它的近似比.最大平分割问题(Max-Bisection Problem)是最大割问题的重要变形. 本论文考虑最大割问题和最大平分割问题基于半定规划松弛的近似算法.当半定规划松弛的最优解落到二维空间时，Goemans将近似比从0.87856…改进为0.88456.我们得到一个依赖于半定规划松弛的目标值与总权和的比值的近似比曲线，此曲线的最低点为0.88456，当半定规划松弛的目标值与总权和的比值在0.5000到0.9044之间时，利用Gegenbauer多项式舍入技巧，我们改进Goemans和Williamson[11]的近似比曲线.进一步地，我们考虑最大平分割问题，在此问题中增加了选取的顶点集合与剩余顶点集合的基数相等的要求.我们同样考虑了最大平分割问题半定规划松弛的最优解落到二维空间的情形，并利用前述的Gegenbauer多项式舍入技巧得到0.7091-近似算法.