  


Approximation Algorithms for Indefinite Complex Quadratic Maximization Problems
Yongwei Huang (ywhuangse.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 realvalued), 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.56approximation 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 (Semidefinite Programming ) Citation: Technical Report SEEM200503, Department of Systems Engineering & Engineering Management, The Chinese University of Hong Kong, 2005 Download: [PDF] Entry Submitted: 07/22/2005 Modify/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  