{"entities":{"Q877200":{"pageid":879048,"ns":120,"title":"Item:Q877200","lastrevid":50076070,"modified":"2026-01-12T21:17:49Z","type":"item","id":"Q877200","labels":{"en":{"language":"en","value":"On approximating complex quadratic optimization problems via semidefinite programming relaxations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5145060"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q877200$1A2E5A29-8EE8-4DC6-8466-7BB1C69393B3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5e5483f232c30d72da9e17c8d5c3d9a1a9d01582","datavalue":{"value":{"text":"On approximating complex quadratic optimization problems via semidefinite programming relaxations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q877200$179C6615-54AD-401D-9153-F7529116DE75","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e103d99ab50382205648270a9f7671be2bfbf4a3","datavalue":{"value":"1192.90134","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q877200$731B9B8D-9EEB-4493-9DA7-6E0C178ACC44","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a79b9e8e4a86b3b6272a2d543345119dee06bf37","datavalue":{"value":{"entity-type":"item","numeric-id":644907,"id":"Q644907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q877200$9312A944-2A7D-4AFB-AD61-AA9B9C2F864A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f722a9d373eb3dc93c3a37caf61c6de6dd0a5d2b","datavalue":{"value":{"entity-type":"item","numeric-id":173845,"id":"Q173845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q877200$8D8EC19E-9CFB-48E2-9E80-DF14A4FA62E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cd874b9a46dbdafe06bbca74951679444a15cc5d","datavalue":{"value":{"entity-type":"item","numeric-id":1697894,"id":"Q1697894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q877200$513075E6-D6A0-4338-A7AC-4764EA120191","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q877200$A3C3123A-A0DD-4F43-9934-8CFC4C08166D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c162f292d55d8cae8f707bd4c33cce3b2222d9aa","datavalue":{"value":{"time":"+2007-04-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q877200$995350B3-6B64-4618-8C45-0610B8271EFE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f86a62ae43ffb3e2538f19ca4096e8a1ce1bc51a","datavalue":{"value":"The paper is concerned with both a NP-hard discrete and a continuous quadratic optimization problem in the complex Hermitian form, and it provides a generic algorithm as well as a unified approach for the approximation of these problems by semidefinite programming (SDP) relaxations. An example of the studied type of discrete problem is the MAX-3-CUT problem with a positive semidefinite Laplacian matrix, and examples of the continuous problem occur in connection with robust optimization and in control theory. For the discrete problem a \\((k\\sin (\\pi /k))^{2}/(4\\pi )\\)-algorithm is given under the assumptions that the decision variables are \\(k\\)-ary and the objective matrix is positive semidefinite. For the continuous problem with positive semidefinite objective matrix the well-known \\(\\pi /4\\)-approximation result is obtained, however, in comparison to earlier proofs of this result, by a simpler analysis and within a more general framework for such problems. Moreover it is shown that, in the latter case, the gap between the optimal values of the given problem and its SDP relaxation can be arbitrarily close to \\(\\pi /4\\). At last, the new approach is used to demonstrate that an \\(\\Omega (1/\\log (n))\\)-approximation algorithm can be derived when the matrix in the quadratic objective of the continuous problem is not positive semidefinite.","type":"string"},"datatype":"string"},"type":"statement","id":"Q877200$AFFA184E-CE28-45AB-915C-7FFFAB9717B5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"694e2c1c97a8b80b8f06da737a7d5c9a1cc0fd1a","datavalue":{"value":{"entity-type":"item","numeric-id":235025,"id":"Q235025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q877200$3654DEF3-82C9-4A7E-950E-40D4AB0A049B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4d4b880941bb65ec306ce9d3141ff7e82566f56","datavalue":{"value":"90C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q877200$F15D8EE9-981A-4C30-83FE-9D495728C380","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q877200$0FC928AE-284A-4CBD-9508-E2B6ECCAA923","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"747ca2a29edc80ef77db4b4376cee27cb80d39e3","datavalue":{"value":"90C22","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q877200$EEEFD931-412A-4E33-830C-10139C251A9A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"eed3086b9edd626581feeecc039661a5cb401f67","datavalue":{"value":"5145060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q877200$1B194320-7BE7-43E5-8A21-D2AB044494E8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1225698ee1ce6f530c07801bcb558970357b68ea","datavalue":{"value":"Hermitian quadratic functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q877200$66C91796-B78B-4FA1-B6A9-77598F59E17E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7cc7d46eedb65be6abe8e2aa947543e50e63afce","datavalue":{"value":"complex quadratic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q877200$D0AE1965-6AB1-49E7-80B9-A501BB1813D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f63e3b27677921597fa0f5b3d475d2c273b12756","datavalue":{"value":"complex semidefinite programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q877200$7910A835-CE7B-466C-9678-3D46159B4906","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1b522cacc7c5e57e459064e347692720a3477c8","datavalue":{"value":"Grothendieck's inequality","type":"string"},"datatype":"string"},"type":"statement","id":"Q877200$33473779-70AA-4B89-AAA6-79720654E997","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q877200$A1D86553-306B-4B38-A1AD-9966B5C3D0C5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"185112593317e58bee51274680a0cb492faa85cc","datavalue":{"value":"https://doi.org/10.1007/s10107-006-0064-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q877200$650E9D67-465E-4289-A268-90746E5A19A7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1683c128e3cfdbcea242025103e9ad1e8041b5cb","datavalue":{"value":"W4236826464","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q877200$853AC3AE-A4BE-4516-A2CA-DE62172A50D6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed41499c3067021ac3853ebafca553badbd43563","datavalue":{"value":{"entity-type":"item","numeric-id":5901109,"id":"Q5901109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q877200$D2E560B9-4EAB-4D5D-A100-8DFF4F9DD347","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ead913ff1641682037bf8635150847f960f2f693","datavalue":{"value":{"entity-type":"item","numeric-id":3580948,"id":"Q3580948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q877200$329D1284-36C5-4F62-AA43-4A9E6C153793","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1f5af4b5107481095c1f10f4e99b9c93c673d4d","datavalue":{"value":{"entity-type":"item","numeric-id":5704138,"id":"Q5704138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q877200$F6F86E40-6E9C-4CAA-B453-291DC68EA2B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f503f6e8d6c9bf5f7d668edeb911a6daa4be963","datavalue":{"value":{"entity-type":"item","numeric-id":679447,"id":"Q679447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q877200$D1F9225A-EE84-4EE4-BEED-37A81CAE147D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ed65c4940d30c8b4fd3f1136f9701dfb3088ee4","datavalue":{"value":{"entity-type":"item","numeric-id":4517107,"id":"Q4517107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q877200$381E828D-653F-4668-A877-2137CA4267AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7f992e855d8b9b42f253fc7f7d98a5e06e39cb4","datavalue":{"value":{"entity-type":"item","numeric-id":4369893,"id":"Q4369893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q877200$D1C5DD4C-E9DE-45BC-AD47-4A77413F6EA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bed8309b2ce4a1a66af1ed0a4342239ee8b5ff21","datavalue":{"value":{"entity-type":"item","numeric-id":1887719,"id":"Q1887719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q877200$6B9A28FB-5A47-43D9-BB75-73C0BCBEC326","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85859d4bf1a3e88a94a43f3e1ce8b0cfd1f2c77b","datavalue":{"value":{"entity-type":"item","numeric-id":3002852,"id":"Q3002852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q877200$CDF13DB0-D75F-47A4-8C2C-682F6733DECC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a051797ce5bb7fe63e77605da657170a5ad0c83","datavalue":{"value":{"entity-type":"item","numeric-id":1968792,"id":"Q1968792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q877200$8742C46B-00A2-4CBC-A721-44CEF0CA45EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b49211240c37a80a009c794b5700fc11c08e0547","datavalue":{"value":{"entity-type":"item","numeric-id":1223583,"id":"Q1223583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q877200$F371DBBA-1207-4A21-A649-4EBD02D09B39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82e839d9eb051852db01759c8ec81229ec802ab3","datavalue":{"value":{"entity-type":"item","numeric-id":4396072,"id":"Q4396072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q877200$28757D64-B401-4419-9AB4-9BA333288C3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b68667d0575a943560173a0a00df96818faa3b7","datavalue":{"value":{"entity-type":"item","numeric-id":4877532,"id":"Q4877532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q877200$7F76BF15-1EA4-44AF-B1C9-021F5A6C7F24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e104214af32a891dd7b7a304e04bb5b5865d95e9","datavalue":{"value":{"entity-type":"item","numeric-id":1572673,"id":"Q1572673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q877200$351F1AD8-071C-45D0-B1C1-3353B4986C59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67eba8f3132b9270a5b87d036aeb6888800b767a","datavalue":{"value":{"entity-type":"item","numeric-id":5470223,"id":"Q5470223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q877200$E0187091-BF0F-4049-A6F1-9527E18E8462","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"541f23beec852f967ab085f9898a62b1e3018e3d","datavalue":{"value":"10.1007/S10107-006-0064-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q877200$221E8FB2-8839-49D1-B07F-C35C47102958","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b0e368ddbc3c92d663ec39d9ce08dc9fb455190","datavalue":{"value":{"entity-type":"item","numeric-id":3596347,"id":"Q3596347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3dcbe31b276a908c05aff0076612b2edf64757d5","datavalue":{"value":{"amount":"+0.96956068277359","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q877200$E97C65F3-4DE7-4A6D-9787-4E5D410A7EE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78be2cf9e4bfb4fe38e2a3dba73ae2890d44c760","datavalue":{"value":{"entity-type":"item","numeric-id":5470223,"id":"Q5470223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0bd136c0a1c3d868aec1eee0512575f6ef80dea8","datavalue":{"value":{"amount":"+0.8791868686676025","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q877200$3D1989F1-2DA6-4101-80BB-4901303FBB15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f60937a43a20fec72fd2039fc31b5a2346f15df8","datavalue":{"value":{"entity-type":"item","numeric-id":1575069,"id":"Q1575069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d3339cdcc6f3c09a21c49231f8612f1e20485fe","datavalue":{"value":{"amount":"+0.8665182590484619","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q877200$20A0F43F-4D1B-4719-AD24-A10E71FDBCD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2171a0658512e88bf40b0722c8e7d939068a481","datavalue":{"value":{"entity-type":"item","numeric-id":5444278,"id":"Q5444278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58be5e62d662f9f06716e9386dbc29e7182817bc","datavalue":{"value":{"amount":"+0.8665180206298828","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q877200$077405A7-E8D5-465F-8427-C297A3877753","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa6727bfb2062aa13a29bcbe66b55e9049e16512","datavalue":{"value":{"entity-type":"item","numeric-id":2475315,"id":"Q2475315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a413f6ff9ec7a2873b3f18987e881f0e2aa45f7","datavalue":{"value":{"amount":"+0.8419725298881531","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q877200$464E1ED3-B8CA-4B8A-94DB-2B95315F2EE9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:877200","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:877200"}}}}}