Optimization Online


Approximation Algorithms for Indefinite Complex Quadratic Maximization Problems

Yongwei Huang (ywhuang***at***se.cuhk.edu.hk)
Shuzhong Zhang (zhang***at***se.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society