Approximation algorithms for indefinite complex quadratic maximization problems

In this paper, we consider the following indefinite complex quadratic maximization problem: maximize z ^H Qz, subject to z _k ∈ ? and z _k ^m = 1, k = 1,...,n, where Q is a Hermitian matrix with tr Q = 0, z ∈ ? ⁿ is the decision vector, and m ? 3. An Ω(1/log n) approximation algorithm is presented for such problem. Furthermore, we consider the above problem where the objective matrix Q is in bilinear form, in which case a $ 0.7118\left( {\cos \frac{\pi } {m}} \right)^2 $ approximation algorithm can be constructed. In the context of quadratic optimization, various extensions and connections of the model are discussed.