Approximation Algorithms for Indefinite Complex Quadratic Maximization Problems

Yongwei Huang (ywhuangse.cuhk.edu.hk)
Shuzhong Zhang (zhangse.cuhk.edu.hk)

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.

Keywords: indefinite Hermitian matrix, randomized algorithms, approximation ratio, semidefinite programming relaxation

Category 1: Combinatorial Optimization (Approximation Algorithms )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Technical Report SEEM2005-03, Department of Systems Engineering & Engineering Management, The Chinese University of Hong Kong, 2005

Download: [PDF]

Entry Submitted: 07/22/2005
Entry Accepted: 07/25/2005
Entry Last Modified: 07/22/2005

Modify/Update this entry