Approximation algorithms for indefinite complex quadratic maximization problems

Yong wei Huang, Shuzhong Zhang

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

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

Original languageEnglish (US)
Pages (from-to)2697-2708
Number of pages12
JournalScience China Mathematics
Volume53
Issue number10
DOIs
StatePublished - 2010

Bibliographical note

Funding Information:
Acknowledgements Research by the second author was supported by Hong Kong RGC Earmarked Grant (Grant No. CUHK418406) and National Natural Science Foundation of China (Grant No. 10771133). Part of the first author’s work was done when he was in Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong.

Keywords

  • approximation ratio
  • indefinite Hermitian matrix
  • randomized algorithms
  • semidefinite programming relaxation

Fingerprint Dive into the research topics of 'Approximation algorithms for indefinite complex quadratic maximization problems'. Together they form a unique fingerprint.

Cite this