Approximation algorithms for indefinite complex quadratic maximization problems

Yong wei Huang; Shuzhong Zhang

doi:10.1007/s11425-010-3087-7

Approximation algorithms for indefinite complex quadratic maximization problems

Yong wei Huang, Shuzhong Zhang

Industrial and Systems Engineering

Research output: Contribution to journal › Article › peer-review

14 Scopus citations

Abstract

In this paper, we consider the following indefinite complex quadratic maximization problem: maximize z^HQ_z, subject to z_k ∈ ℂ and z_k^m = 1, k = 1,...,n, where Q is a Hermitian matrix with tr Q = 0, z ∈ ℂⁿ 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)² approximation algorithm can be constructed. In the context of quadratic optimization, various extensions and connections of the model are discussed.

Original language	English (US)
Pages (from-to)	2697-2708
Number of pages	12
Journal	Science China Mathematics
Volume	53
Issue number	10
DOIs	https://doi.org/10.1007/s11425-010-3087-7
State	Published - 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

Publisher link

10.1007/s11425-010-3087-7

Find It

Find It at U of M Libraries

Cite this

@article{a09005d1c8b8429aab442084c6f35d82,

title = "Approximation algorithms for indefinite complex quadratic maximization problems",

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.",

keywords = "approximation ratio, indefinite Hermitian matrix, randomized algorithms, semidefinite programming relaxation",

author = "Huang, {Yong wei} and Shuzhong Zhang",

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{\textquoteright}s work was done when he was in Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong.",

year = "2010",

doi = "10.1007/s11425-010-3087-7",

language = "English (US)",

volume = "53",

pages = "2697--2708",

journal = "Science China Mathematics",

issn = "1674-7283",

publisher = "Science China Press",

number = "10",

}

TY - JOUR

T1 - Approximation algorithms for indefinite complex quadratic maximization problems

AU - Huang, Yong wei

AU - Zhang, Shuzhong

N1 - 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.

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

KW - approximation ratio

KW - indefinite Hermitian matrix

KW - randomized algorithms

KW - semidefinite programming relaxation

UR - http://www.scopus.com/inward/record.url?scp=85027947939&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85027947939&partnerID=8YFLogxK

U2 - 10.1007/s11425-010-3087-7

DO - 10.1007/s11425-010-3087-7

M3 - Article

AN - SCOPUS:85027947939

SN - 1674-7283

VL - 53

SP - 2697

EP - 2708

JO - Science China Mathematics

JF - Science China Mathematics

IS - 10

ER -

Approximation algorithms for indefinite complex quadratic maximization problems

Abstract

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this