English

运筹学学报

• 运筹学 • 上一篇    下一篇

最大割问题和最大平分割问题基于半定规划松弛的近似算法

孙婷1  李改弟1,*  徐文青1,2   

  1. 1. 北京工业大学应用数理学院,  北京 100124 2. 加州州立大学长滩分校数学与统计系, 长滩 CA 90840, 美国
  • 收稿日期:2015-07-17 出版日期:2016-09-15 发布日期:2016-09-15
  • 通讯作者: 李改弟 ligd@bjut.edu.cn
  • 基金资助:

    国家自然科学基金(No.11201013), 北京工业大学应用数理学院数理基金

Approximation algorithms for max cut and  max bisection problems using semi-definite programming relaxations

SUN Ting1   LI Gaidi1,*  XU Wenqing1,2   

  1. 1. College of Applied Sciences, Beijing University of Technology, Beijing 100124, China 2. Department of Mathematics and Statistics, California State University, Long Beach CA 90840, USA
  • Received:2015-07-17 Online:2016-09-15 Published:2016-09-15

PDF

479

摘要：

考虑每条边具有非负权重的无向图, 最大割问题要求将顶点集划分为两个集合使得它们之间的边的权重之和最大. 当最大割问题半定规划松弛的最优解落到二维空间时, Goemans将近似比从0.87856...改进为0.88456. 依赖于半定规划松弛的目标值与总权和的比值的曲线, 此曲线的最低点为0.88456, 当半定规划松弛的目标值与总权和的比值在0.5到0.9044之间时, 利用Gegenbauer多项式舍入技巧, 改进了Zwick的近似比曲线. 进一步, 考虑最大割问题的重要变形------最大平分割问题, 在此问题中增加了划分的两部分的点数相等的要求. 同样考虑了最大平分割问题半定规划松弛的最优解落到二维空间的情形, 并利用前述的Gegenbauer多项式舍入技巧得到0.7091-近似算法.

关键词: 最大割问题, 最大平分割问题, 近似算法, 半定规划

Abstract:

Given an undirected graph with nonnegative weight for each edge, the max cut problem is to partition its vertex set into two parts such that the total weight of crossing edges is maximized. When the optimal solution of its Service Design Package (SDP) relaxation lies in a two-dimension space, Goemans improved the approximation ratio from 0.87856... to 0.88456. Using the Gegenbauer polynomials rounding technique, we obtain an approximation curve depending on the ratio between the optimal value of the SDP relaxation and the total weight,  which has the lowest point 0.88456. We further improve the  approximation ratio curve when the ratio varies from 0.5 to 0.9044. Furthermore, we consider an important variant of the max cut problem, the max bisection problem, in which the equal cardinality constraint for the two parts in the partition is imposed. We also consider the case that the optimal solution of the SDP relaxation for the Max Bisection problem lies in a two-dimension space and obtain a 0.7091-approximation for this variant by using the aforementioned Gegenbauer polynomials rounding technique.

Key words: max cut problem, max bisection problem, approximation algorithm, semidefinite programming