Quadratic maximization and semidefinite relaxation

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 ??-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.

Authors and Affiliations

1. Department of Systems Engineering & Engineering Management, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong, e-mail: zhang@se.cuhk.cuhk.edu.hk, , , , , , HK

   Shuzhong Zhang

Received: September 10, 1998 / Accepted: February 12, 1999¶Published online February 23, 2000

Reprints and permissions