{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,10]],"date-time":"2026-10-10T00:22:33Z","timestamp":1791591753069,"version":"4.3.4"},"reference-count":15,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2006,1]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/04061341x","type":"journal-article","created":{"date-parts":[[2006,1,16]],"date-time":"2006-01-16T21:00:26Z","timestamp":1137445226000},"page":"871-890","source":"Crossref","is-referenced-by-count":178,"title":["Complex Quadratic Optimization and Semidefinite Programming"],"prefix":"10.1137","volume":"16","author":[{"given":"Shuzhong","family":"Zhang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yongwei","family":"Huang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177700391"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"H. H. Andersen, M. H\u00f8jbjerre, D. S\u00f8rensen, and P. S. Eriksen,\n                      Linear and Graphical Models for the Multivariate Complex Normal Distribution\n                      , Lecture Notes in Statist. 101, Springer\u2010Verlag, New York, 1995.","DOI":"10.1007\/978-1-4612-4240-6"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.3.497.16392"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"DimitrisBertsimas, YinyuYe, Semidefinite relaxations, multivariate normal distributions, and order statistics, Kluwer Acad. Publ., Boston, MA, 1998, 1\u201319MR1665415","DOI":"10.1007\/978-1-4613-0303-9_24"},{"key":"R5","unstructured":"M. Charikar and A. Wirth,\n                      Maximizing quadratic programs: Extending Grothendieck\u2019s inequality\n                      , in Proceedings of the 45th Annual FOCS, 2004."},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523688"},{"key":"R7","volume-title":"Computers and intractability","author":"Garey Michael","year":"1979"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.012"},{"key":"R10","unstructured":"Z. Q. Luo, X. D. Luo, and M. Kisialiou,\n                      An efficient quasi\u2010maximum likelihood decoder for PSK signals\n                      , in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP \u201903), Vol. 6, 2003, pp. 561\u2013564."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1080\/10556789808805690"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"A. So, J. Zhang, and Y. Ye,\n                      On approximating complex quadratic optimization problemsvia semidefinite programming relaxations\n                      , in Proceedings of the 11th Conference on Integer Programming and Combinatorial Optimization, Lecture Notes in Comput. Sci. 3509, M. J\u00fcnger and V. Kaibel, eds., Springer\u2010Verlag, Berlin, 2005, pp. 125\u2013135.","DOI":"10.1007\/11496915_10"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1109\/9.661609"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050087"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050006"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/04061341X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:17:29Z","timestamp":1787332649000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/04061341X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":15,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1137\/04061341X"],"URL":"https:\/\/doi.org\/10.1137\/04061341x","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1]]}}}