Optimization Online


Approximation Bounds for Quadratic Maximization with Semidefinite Programming Relaxation

Dachuan Xu (xudc***at***sina.com)
Shuzhong Zhang (zhang***at***se.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 )


Download: [Postscript]

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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society