Approximation Bounds for Quadratic Maximization with Semidefinite Programming Relaxation

Dachuan Xu (xudcsina.com)
Shuzhong Zhang (zhangse.cuhk.edu.hk)

Abstract: In this paper, we consider a class of quadratic maximization problems. One important instance in that class is the famous quadratic maximization formulation of the max-cut problem studied by Goemans and Williamson. Since the problem is NP-hard in general, following Goemans and Williamson, we apply the approximation method based on the semidefinite programming (SDP) relaxation. For a subclass of the problems, including the ones studied by Helmberg and Zhang, 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 0.87856 being a uniform lower bound. In light of this new bound, we study the original max-cut problem and show that the actual worst-case performance ratio of the SDP relaxation approach (with the triangle inequalities added) is at least $0.87856+\delta_d$, where $\delta_d>0$ is a constant depending on the problem dimension and data. Recall that Karloff showed that for any positive $\epsilon>0$ there is an instance of the max-cut problem such that the SDP relaxation (with triangle inequalities) bound is worse than $\alpha+\epsilon$. Hence our improvement is in this sense best possible for the Goemans and Williamson type approach to the max-cut problem.

Keywords: quadratic maximization, semidefinite programming relaxation, approximation algorithm, performance ratio

Category 1: Combinatorial Optimization (Approximation Algorithms )

Citation:

Download: [Postscript]

Entry Submitted: 01/19/2003
Entry Accepted: 01/20/2003
Entry Last Modified: 01/19/2003

Modify/Update this entry