1998-12-03
Quadratic maximization and semidefinite relaxation
Publication
Publication
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.
Additional Metadata | |
---|---|
, , , | |
hdl.handle.net/1765/1541 | |
Econometric Institute Research Papers | |
Organisation | Erasmus School of Economics |
Zhang, S. (1998). Quadratic maximization and semidefinite relaxation (No. EI 9833). Econometric Institute Research Papers. Retrieved from http://hdl.handle.net/1765/1541 |