  


Approximation Bounds for Quadratic Maximization with Semidefinite Programming Relaxation
Dachuan Xu (xudcsina.com) 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 maxcut problem studied by Goemans and Williamson. Since the problem is NPhard 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 worstcase performance ratio at least 0.87856. In fact, the estimated worstcase 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 maxcut problem and show that the actual worstcase 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 maxcut 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 maxcut 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 Modify/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  