Quadratic maximization and semidefinite relaxation

Quadratic maximization and semidefinite relaxation

0.00 Avg rating0 Votes
Article ID: iaor20013656
Country: Germany
Volume: 87
Issue: 3
Start Page Number: 453
End Page Number: 465
Publication Date: Jan 2000
Journal: Mathematical Programming
Authors:
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 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.

Reviews

Required fields are marked *. Your email address will not be published.