The DOI matches its Crossref record; 1 of the 1 references it cites were found in a registry or an index.
Complex Quadratic Optimization and Semidefinite Programming
Abstract
In this paper we study the approximation algorithms for a class of discrete quadratic optimization problems in the Hermitian complex form. A special case of the problem that we study corresponds to the max-3-cut model used in a recent paper of Goemans and Williamson J. Comput. System Sci., 68 (2004), pp. 442-470]. We first develop a closed-formformula to compute the probability of a complex-valued normally distributed bivariate random vector to be in a given angular region. This formula allows us to compute the expected value of a randomized (with a specific rounding rule) solution based on the optimal solution of the complex semidefinite programming relaxation problem. In particular, we present an $[m^2(1-\cos\frac{2\pi}{m})/8\pi]$-approximation algorithm, and then study the limit of that model, in which the problem remains NP-hard. We show that if the objective is to maximize a positive semidefinite Hermitian form, then the randomization-rounding procedure guarantees a worst-case performance ratio of $\pi/4 \approx 0.7854$, which is better than the ratio of $2/\pi \approx 0.6366$ for its counterpart in the real case due to Nesterov. Furthermore, if the objective matrix is real-valued positive semidefinite with nonpositive off-diagonal elements, then the performance ratio improves to 0.9349.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
Cited by
Semidefinite Relaxation of Quadratic Optimization Problems
Luo, Z.-Q., Ma, W.-K., So, A., Ye, Y., & Zhang, S. (2010) · IEEE Signal Processing Magazine · doi:10.1109/msp.2010.936019 · Cited by 3,715
Self-citationQuality of Service and Max-Min Fair Transmit Beamforming to Multiple Cochannel Multicast Groups
Karipidis, E., Sidiropoulos, N. D., & Luo, Z.-Q. (2008) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2007.909010 · Cited by 585
Phase recovery, MaxCut and complex semidefinite programming
Waldspurger, I., d’Aspremont, A., & Mallat, S. (2015) · Mathematical Programming · doi:10.1007/s10107-013-0738-9 · Cited by 573
Liao, W.-C., Chang, T.-H., Ma, W.-K., & Chi, C.-Y. (2011) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2010.2094610 · Cited by 390
Realizing the classical XY Hamiltonian in polariton simulators
Berloff, N. G., Silva, M., Kalinin, K., Askitopoulos, A., Töpfer, J. D., Cilibrizzi, P., Langbein, W., & Lagoudakis, P. G. (2017) · Nature Materials · doi:10.1038/nmat4971 · Cited by 341
Metadata
- Authors
- Zhang, S., & Huang, Y.
- Venue
- SIAM Journal on Optimization
- Published
- 2006-01
- Volume
- 16
- Issue
- 3
- Pages
- 871-890
- ISSN
- 1052-6234 (ISSN-L)
- 1095-7189
- OpenAlex
- W2007104311
- Cited by
- 205
- References
- 1
- FWCI
- 3.98
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Complex Quadratic Optimization and Semidefinite Programming. https://app.cochat.ai/papers/10.1137/04061341x
- The paper
- Zhang, S., & Huang, Y. (2006). Complex Quadratic Optimization and Semidefinite Programming. SIAM Journal on Optimization. https://doi.org/10.1137/04061341x
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.