Title: 
Approximation Algorithms for Indefinite Complex Quadratic Maximization Problems


Authors:
Yongwei Huang
Department of Systems Engineering and Engineering Management
The Chinese University of Hong Kong
Shatin, Hong Kong.

Shuzhong Zhang
Department of Systems Engineering and Engineering Management
The Chinese University of Hong Kong
Shatin, Hong Kong


Abstract:
In this paper we consider the following two types of complex
quadratic maximization problems: (i) maximize $z^{\HH} Q z$,
subject to $z_k^m=1$, $k=1,...,n$, where $Q$ is a Hermitian matrix
with $\tr Q=0$ and $z\in \C^n$ is the decision vector; (ii)
maximize $\re y^{\HH}Az$, subject to $y_k^m=1$, $k=1,...,p$, and
$z_l^m=1$, $l=1,...,q$, where $A\in \C^{p\times q}$ and $y\in
\C^p$ and $z\in \C^q$ are the decision vectors. In the real cases
(namely $m=2$ and the matrices are all real-valued), such problems
were recently considered by Charikar and Wirth 
and Alon and Naor respectively. In particular, Charikar and
Wirth presented an $\Omega(1/\log n)$ approximation algorithm 
for Problem (i) in the real case, and Alon and Naor presented 
a 0.56-approximation algorithm for Problem (ii) in the real case. 
In this paper, we propose an $\Omega(1/\log n)$ approximation algorithm for the
general version of complex Problem (i), and a
$\left(\frac{m^2(1-\cos\frac{2\pi}{m})}{4\pi}-1\right)$-approximation
algorithm for the general version of complex Problem (ii). For the limit
and continuous version of complex Problem (ii) ($m\rightarrow\infty$),
we further show that a 0.7118 approximation ratio can be achieved.