- 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/2003Entry Accepted: 01/20/2003Entry Last Modified: 01/19/2003Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.