Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation  

作　　者：Da-chuan XU~(1+) Shu-zhong ZHANG~2 1 Department of Applied Mathematics,Beijing University of Technology,Beijing 100022,China 2 Department of Systems Engineering and Engineering Management,The Chinese University of Hong Kong,Shatin,Hong Kong,China 

出　　处：《Science China Mathematics》2007年第11期1583-1596,共14页中国科学：数学（英文版）

基　　金：This work was supported by the National Natural Science Foundation of China (Grant No.10401038);Startup Grant for Doctoral Research of Beijing University of Technology and Hong Kong RGC Earmarked Grant CUHK4242/04E

摘　　要：In this paper,we consider a class of quadratic maximization problems.For a subclass of the problems,we show that the SDP relaxation approach yields an approximation solution with the worst-case performance ratio at leastα=0.87856….In fact,the estimated worst-case performance ratio is dependent on the data of the problem withαbeing a uniform lower bound.In light of this new bound,we show that the actual worst-case performance ratio of the SDP relaxation approach (with the triangle inequalities added) is at leastα+δ_d if every weight is strictly positive,whereδ_d>0 is a constant depending on the problem dimension and data.In this paper,we consider a class of quadratic maximization problems.For a subclass of the problems,we show that the SDP relaxation approach yields an approximation solution with the ratio is dependent on the data of the problem with α being a uniform lower bound.In light of this new bound,we show that the actual worst-case performance ratio of the SDP relaxation approach (with the triangle inequalities added) is at least α + δd if every weight is strictly positive,where δd ＞ 0 is a constant depending on the problem dimension and data.

关 键 词：quadratic maximization max-cut problem semideflnite programming relaxation approximation algorithm performance ratio 

分 类 号：O221[理学—运筹学与控制论]