{"entities":{"Q4407449":{"pageid":6437048,"ns":120,"title":"Item:Q4407449","lastrevid":109089635,"modified":"2026-11-11T11:05:56Z","type":"item","id":"Q4407449","labels":{"en":{"language":"en","value":"Semidefinite programs and combinatorial optimization"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1944141"}},"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":"Q4407449$FF24F065-3F48-482D-A8B0-DF8A92C5187F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"da643c8edeb6697ba1209832a3530da156fcde46","datavalue":{"value":"1040.90032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4407449$45F1984F-C6F7-43C5-8523-97375E920DFD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"16179fdf9dd6b498fad3f9e77d522b325315bc5c","datavalue":{"value":{"time":"+2003-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4407449$5637377D-F04D-4747-A44F-24FB86D47401","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"747ca2a29edc80ef77db4b4376cee27cb80d39e3","datavalue":{"value":"90C22","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4407449$4EDA6FCB-813D-4A1E-94C0-0C4E70158EC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4407449$7B20C7C9-F343-456D-9948-575A023FA1D6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"88ce47bc5d854352928d6223891559b834ef3002","datavalue":{"value":"1944141","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4407449$CC4D162A-8C8A-4179-9048-D5E0DA6A69FA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8aad77c6771da2e7d7825e7e018fab27fceeb5f9","datavalue":{"value":"Shannon capacity","type":"string"},"datatype":"string"},"type":"statement","id":"Q4407449$E5D881BF-DBD1-4431-B98E-33F76D3C81B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f07e32531c22a9eb615d331111f7d6a65293beb9","datavalue":{"value":"maximum cuts","type":"string"},"datatype":"string"},"type":"statement","id":"Q4407449$71276F9B-D079-4666-9D28-4E38C1E5197A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e486b6bef051e5de3b5105f0d954e7a043162e0b","datavalue":{"value":"discrete linear and quadratic programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q4407449$40019D30-5A64-4F9F-A7F7-0D7B7011A871","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a35934e8ce485ec9fae66d5705b3031088030da8","datavalue":{"value":"semidefinite programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q4407449$C5C92CF4-AE13-43F1-BE48-A5FEDBC651E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6135ceafed3292f6b66e098192375f7d5b754046","datavalue":{"value":"inference rules","type":"string"},"datatype":"string"},"type":"statement","id":"Q4407449$38BC3B4C-E9B6-4D8F-BEB7-1C5DE640F7C0","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":"Q4407449$CD019BE4-8B4B-4DEF-A940-4451502E4D06","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"201364cbbc61e0d0a85431778d2e1c2e76306b69","datavalue":{"value":{"entity-type":"item","numeric-id":6480584,"id":"Q6480584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4407449$0137047B-B783-4B29-A429-B57825A0F729","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34fed59f5a0002a2c7fab94221ad7e70d65ee49a","datavalue":{"value":{"entity-type":"item","numeric-id":5906394,"id":"Q5906394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"787b7a4995733522c09afe138ae55a7dd589c38b","datavalue":{"value":{"amount":"+0.8975517749786377","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":"Q4407449$C64BD922-A0C6-464E-8262-B5A83657007E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea08f7184d53e2458282c6aae0331ce4eea5d4fb","datavalue":{"value":{"entity-type":"item","numeric-id":2889301,"id":"Q2889301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6bd43da8587f157dfe63689aa449b397e244a424","datavalue":{"value":{"amount":"+0.8891550302505493","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":"Q4407449$95D6B361-EDE7-428C-B824-8834D3DB536C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba815799657ae8e92a64e5501b1b61cb79cac59b","datavalue":{"value":{"entity-type":"item","numeric-id":5292090,"id":"Q5292090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"57bb856523e06f73ac2ba8e88456445c9bc90fad","datavalue":{"value":{"amount":"+0.8840233683586121","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":"Q4407449$46B07041-921A-44B4-BF12-3C7A93984B65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f18b6d80c1107c64aaf60b33ee73bf863400a6e","datavalue":{"value":{"entity-type":"item","numeric-id":1365053,"id":"Q1365053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1eb07907d52d947e38b510e28a9b643091de44d","datavalue":{"value":{"amount":"+0.8811874985694885","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":"Q4407449$B7B707EB-2AAA-43A4-AAC0-C97F863DBDE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6349fa6057d7155aa124492dcfe02bfaf04873a","datavalue":{"value":{"entity-type":"item","numeric-id":611309,"id":"Q611309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a33fee9a46d1f3c8614c720d1b35fa0eb4741445","datavalue":{"value":{"amount":"+0.8648182153701782","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":"Q4407449$D737066A-2383-4F46-B29C-5FD8465127C6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d2f5c2919386e09037cc65d4cfb5a9ff123e0fc0","datavalue":{"value":{"text":"Semidefinite programs and combinatorial optimization","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4407449$15A522DF-6F54-4B8C-B19D-27D76FC7C9DA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c82de03a72aeb1060b4725682c7058e4e73dfff4","datavalue":{"value":"The author surveys semidefinite optimization mainly as relaxation of discrete optimization problems. He starts with two examples, a proof and an approximation algorithm, where semidefinite optimization plays an important role. Still among the preliminaries, the author surveys some areas which play a role in semidefinite optimization: linear algebra, linear programming, and polyhedral combinatorics. After introducing semidefinite programs and discussing some of their basic properties, he shows that semidefinite programs arise in a variety of ways: as certain geometric extremal problems, as relaxation of combinatorial optimization problems, in optimizing eigenvalue bounds in graph theory, as stability problems in engineering. Next, he shows through examples from graph theory, number theory, and logic how semidefinite optimization can be used in proofs as well in the design of approximation algorithms. In Chapter 6.7 the authors tries to put the combinatorial applications of semidefinite optimization in a broader perspective. Several roadblocks are described in Chapter 6.8. For the entire collection see [Zbl 1005.00014].","type":"string"},"datatype":"string"},"type":"statement","id":"Q4407449$7B9EDD8A-478F-4ADB-9709-0E3D83E5AACD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Semidefinite programs and combinatorial optimization","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Semidefinite_programs_and_combinatorial_optimization"}}}}}