{"entities":{"Q2712834":{"pageid":2723573,"ns":120,"title":"Item:Q2712834","lastrevid":82806215,"modified":"2026-05-06T22:07:35Z","type":"item","id":"Q2712834","labels":{"en":{"language":"en","value":"Semidefinite and Lagrangian relaxations for hard combinatorial problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1595158"}},"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":"Q2712834$2A12338C-06F7-4E93-8AAF-5270512B5FDA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2cf8be9b84126dcc576c430a951ee7d19d0c95c4","datavalue":{"value":"0999.90031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2712834$A61FF392-E057-4E77-87D2-1820352D3FAE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5c7e0702651d77ffce14e2a1623fbb003c278174","datavalue":{"value":{"entity-type":"item","numeric-id":231088,"id":"Q231088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2712834$C80ACE77-1068-48DD-9DA9-FBC51427D78B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0c3c3eaf5703e506961209d7172352e093b57811","datavalue":{"value":{"time":"+2002-11-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2712834$BA3F399D-1A53-4941-9EFD-CCEC721C0662","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2712834$9DD2BE84-DD9D-4609-A1E6-299B97204F96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"747ca2a29edc80ef77db4b4376cee27cb80d39e3","datavalue":{"value":"90C22","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2712834$F4785E7F-8A98-4973-8DBA-19DBB9A77358","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f77eb516761695b4422a24286b9a75d306ad6f31","datavalue":{"value":"1595158","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2712834$9F66F6B3-0DD0-43D5-ADB7-93673C5B5013","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"143bf4577f18163f9ae96816daff106c906b2eec","datavalue":{"value":"semi-definite relaxations","type":"string"},"datatype":"string"},"type":"statement","id":"Q2712834$A4DF07F7-FE23-47C5-AAD9-449CF76BE3ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c123c988a4455db85cc065f2e06e0a8051be65dd","datavalue":{"value":"combinatorial optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q2712834$A46E8596-F42D-4B5B-9EE2-2DF1811ABEDC","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"c47a3795aa0d5ae54cbaac27b6f9721dd75491ba","datavalue":{"value":{"entity-type":"item","numeric-id":19481,"id":"Q19481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2712834$4174C085-B77B-4036-857F-9B69B093EEE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"dbb9e329bae06fc75a190169b98a1a6ffc561e9d","datavalue":{"value":{"entity-type":"item","numeric-id":13584,"id":"Q13584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2712834$87BAD6AE-AB25-4E0F-A792-176DB51238B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"7c5814a0a3b47b1b5455e3eaa345adcdfd08dbf3","datavalue":{"value":{"entity-type":"item","numeric-id":16192,"id":"Q16192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2712834$86904360-E41E-485B-B2EF-7ACC87AC1A94","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":"Q2712834$7F8B747E-29FE-4B70-BF83-0F373522FB23","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ed13c1961013434cb2ec51b0848ae71954c71501","datavalue":{"value":{"text":"Semidefinite and Lagrangian relaxations for hard combinatorial problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2712834$C76BDDC8-0F50-4967-B8AF-9111CD41EBD0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d510cdb7bb0c60284cacdcb5f53e369a5b4ac887","datavalue":{"value":"This paper presents a recipe and some examples of how to find good semi-definite relaxations for combinatorial optimization problems. The main idea is to look at Lagrangian relaxations of a constrained quadratic formulation of the combinatorial optimization problem. More importantly, the paper argues by example that Lagrangian relaxation yields in some sense the best possible bounds for many problems.NEWLINENEWLINEFor the entire collection see [Zbl 0946.00028].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2712834$2C21D170-22D3-4F24-84B7-60E5BFBAA50B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"410981a1afadda812bc680dfed4766e5e039a80f","datavalue":{"value":{"entity-type":"item","numeric-id":581215,"id":"Q581215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2712834$6EF628B5-DC2F-4EA0-92B2-172359FD0011","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d41962352dfeb592cbe026711b14e0fb02733477","datavalue":{"value":{"entity-type":"item","numeric-id":843394,"id":"Q843394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da11a225eec609b88b8c46df65bbf03284e1f3ad","datavalue":{"value":{"amount":"+0.8052639961242676","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":"Q2712834$F41166A8-E84E-46D0-9C2A-3D2BF6EC9042","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9dcf4b45864d94f95b9b835270ddee00ae8f9ad","datavalue":{"value":{"entity-type":"item","numeric-id":2802546,"id":"Q2802546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99be943ff6a3a43b9a7daeeeb40ab9ef55c03368","datavalue":{"value":{"amount":"+0.8020455241203308","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":"Q2712834$835E62D1-4FA5-466A-939A-63E6FEB8AA6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c151017643fa69f04516bd4654a252e9a8e406c","datavalue":{"value":{"entity-type":"item","numeric-id":5101410,"id":"Q5101410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11cff0b17cf3e2637728bd4e959f9346bc633678","datavalue":{"value":{"amount":"+0.7986207604408264","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":"Q2712834$F5751F8B-28FA-45D3-8D62-51C3B1CB105B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f098b65deb9429ed93d9ef38096389a439f804d2","datavalue":{"value":{"entity-type":"item","numeric-id":1925786,"id":"Q1925786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a812201dfd846ca1192c8c6e5654776100a3a681","datavalue":{"value":{"amount":"+0.7970408201217651","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":"Q2712834$C65FD489-6F9D-423E-B970-1FC3BE661943","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14cd186bb9af4a2bada00bc7ae10dad12fd9b8ca","datavalue":{"value":{"entity-type":"item","numeric-id":4504791,"id":"Q4504791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"caaaf24b9e0c748ee4a1bc20d473d61c4d03a2dd","datavalue":{"value":{"amount":"+0.79465651512146","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":"Q2712834$C7483C1F-A4DC-490E-87DF-BB6D49DE1820","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Semidefinite and Lagrangian relaxations for hard combinatorial problems","badges":[]}}}}}