Quadratic maximization and semidefinite relaxation

Shuzhong Zhang

No EI 9833, Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute

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.

Keywords: Quadratic programming; approximation; polynomial-time solvability; semidefinite programming relaxation (search for similar items in EconPapers)
Date: 1998-12-03
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ems:eureir:1541

Access Statistics for this paper

More papers in Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute Contact information at EDIRC.
Bibliographic data for series maintained by RePub ( this e-mail address is bad, please contact ).