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

摘要

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.