Template-Type: ReDIF-Paper 1.0
Author-Name: Zhang, S.
Author-Name-Last: Zhang
Author-Name-First: Shuzhong
Title: Quadratic maximization and semidefinite relaxation
Abstract: In this paper we study a class of quadratic maximization problems and their semidefinite programming (SDP) relaxation. For a special subclass of the problems we show that the SDP relaxation provides an exact optimal solution. Another subclass, which is ${\\cal NP}$-hard, guarantees that the SDP relaxation yields an approximate solution with a worst-case performance ratio of $0.87856...$. This is a generalization of the well-known result of Goemans and Williamson for the maximum-cut problem. Finally, we discuss extensions of these results in the presence of a certain type of sign restrictions.
Creation-Date: 1998-12-03
Series: RePEc:ems:eureir
Number: EI 9833
Keywords: Quadratic programming, approximation, polynomial-time solvability, semidefinite programming relaxation
Handle: RePEc:ems:eureir:1541