Approximating Quadratic Programs with Postitive Semidefinite Constraints
Report ID: TR-746-06Author: Hazan, Elad / Kale, Satyen
Date: 2006-02-00
Pages: 3
Download Formats: |PDF|
Abstract:
We describe a polynomial time approximation algorithm to the problem of maximizing a quadratic form subject to quadratic constraints specified by PSD matrices. A special case, that has applications for clustering, is optimizing quadratic forms over the unit cube.
Approximation algorithms with similar guarantees are known, and there is evidence that this factor is optimal. The following analysis is particularly simple