- 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/2005Entry Accepted: 07/25/2005Entry Last Modified: 07/22/2005Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.