Approximation algorithms for indefinite complex quadratic maximization problems

作     者：HUANG Yongwei1,& ZHANG Shuzhong2 1Department of Electronic and Computer Engineering,The Hong Kong University of Science and Technology,Kowloon,Hong Kong,China 2Department of Systems Engineering and Engineering Management,The Chinese University of Hong Kong,Shatin,Hong Kong,China 

作者机构：1. Department of Electronic and Computer Engineering The Hong Kong University of Science and Technology Kowloon Hong Kong China2. Department of Systems Engineering and Engineering Management The Chinese University of Hong Kong Shatin Hong Kong China 

出 版 物：《Science China Mathematics》 (中国科学：数学（英文版）)

年 卷 期：2010年第53卷第10期

页      面：2697-2708页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：supported by Hong Kong RGC Earmarked Grant (Grant No.CUHK418406) National Natural Science Foundation of China (Grant No.10771133) 

主　　题：indefinite Hermitian matrix randomized algorithms approximation ratio semidefinite programming relaxation 

摘      要：In this paper,we consider the following indefinite complex quadratic maximization problem: maximize zHQz,subject to zk ∈ C and zkm = 1,k = 1,...,n,where Q is a Hermitian matrix with trQ = 0,z ∈ Cn is the decision vector,and m *** (1/log n) approximation algorithm is presented for such ***,we consider the above problem where the objective matrix Q is in bilinear form,in which case a 0.7118 cos mπ 2approximation algorithm can be *** the context of quadratic optimization,various extensions and connections of the model are discussed.