{"entities":{"Q3002764":{"pageid":3013488,"ns":120,"title":"Item:Q3002764","lastrevid":57572028,"modified":"2026-03-31T11:06:05Z","type":"item","id":"Q3002764","labels":{"en":{"language":"en","value":"Proving integrality gaps without knowing the linear program"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5899241"}},"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":"Q3002764$64769A8D-EF98-401D-9F38-3315809FBEA0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"faf5a0f6be96df20a58c93a41af6106656f06ef7","datavalue":{"value":"1213.68306","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3002764$B0B16FFC-3DDD-4E9D-9872-1368E9E7D091","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9a14bac90927db699ac4af297f1d406f2762c11d","datavalue":{"value":{"entity-type":"item","numeric-id":168581,"id":"Q168581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3002764$BBA397E3-4FCC-46A2-A640-184681DF9097","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fe7535c2a7fbc4354350f3fff626d063ef38fc6d","datavalue":{"value":{"entity-type":"item","numeric-id":230573,"id":"Q230573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3002764$207B46D4-30C3-490C-9529-92986227275A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5fa856eb9cad7c56d02923351b2c4236ede2b614","datavalue":{"value":{"entity-type":"item","numeric-id":6480589,"id":"Q6480589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3002764$3C2BBB6C-055D-4A3D-9480-6EDD97DBD0AF","rank":"normal"},{"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":"Q3002764$F2EB549C-2C46-4737-9233-D3D8E84E5DCE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"11632bef515b8b0af0e8d65098d262d28b5f8c42","datavalue":{"value":{"entity-type":"item","numeric-id":2816408,"id":"Q2816408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3002764$34F55A6C-8596-49D2-A052-3D6451A35F51","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"06770005a3ff7536cedbafe2a793f3c0760af601","datavalue":{"value":{"time":"+2011-05-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3002764$A59C186A-F6F0-4157-96D9-C6A8F5FCD44E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3002764$99BF1B4B-E7DA-434D-938A-937F4886E6E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3002764$E5D7381B-56AA-4071-BBD5-2B1A855456FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"955a6ac68db8c67c1772255c707ed5eb1d2bad2b","datavalue":{"value":"90C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3002764$16001353-FF9B-4208-9921-89F9E8F7E19A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"31a6692f3605c4b1ff517945776ee57d9ae31025","datavalue":{"value":"5899241","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3002764$94AA0648-7BA3-4A06-AE06-DE1ACFCD9F80","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a08efa1a08a750d06fca0196004a17a02a35c592","datavalue":{"value":"linear programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q3002764$1426AC17-5E84-4E77-8990-23EB560AD470","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"51f95efbd0445c23f397467c5e509da28dd67bbc","datavalue":{"value":"inapproximability","type":"string"},"datatype":"string"},"type":"statement","id":"Q3002764$98234A68-7D31-4784-AF1E-9B88EF95F55E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q3002764$27ABD5D9-31D9-40D0-85D5-02CA1032FF06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99974e488eefe65e9a359b970a995a9b6d33d8e8","datavalue":{"value":"NP-hard problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q3002764$1097388E-AE45-44DA-9D78-C5EE659152CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1da82c0572ce92a3057fef279b2dc1142e74dfa","datavalue":{"value":"integrality gaps","type":"string"},"datatype":"string"},"type":"statement","id":"Q3002764$A2B7018B-BDCF-4311-85CC-F9162B2D67EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f193a2e41ab0ffacaf49a36e0002a67ff44d54e","datavalue":{"value":"lift-and-project","type":"string"},"datatype":"string"},"type":"statement","id":"Q3002764$6291EC37-F662-4F4A-8B68-E7E54831955D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aac385c43cc6d982a9dd1fbfee8ab2754a681c11","datavalue":{"value":"vertex cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q3002764$DDC78816-D0C5-4BAD-A85B-619873102F2B","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":"Q3002764$7FF48395-2F19-45B6-AB33-8609CD175EBA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"34008db6bfb3ba3bdee633db1f68c8a220d3318b","datavalue":{"value":"https://doi.org/10.4086/toc.2006.v002a002","type":"string"},"datatype":"url"},"type":"statement","id":"Q3002764$923C8599-52F5-44CD-98B8-93FFCCE3603C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"141d1d4b8288ec7d81ca3073c795aad4f639d389","datavalue":{"value":"W1587123489","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3002764$9A5526E9-69C7-4660-9997-F3235A0D4CD3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a7b31278b16795a69e2148bb04b31b3c212daa51","datavalue":{"value":"10.4086/TOC.2006.V002A002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3002764$2958FEF2-4F52-435F-A4F2-2B17685FBE9D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ce946bd6977d85b696e8a8ade264d2fac7aa84b","datavalue":{"value":{"entity-type":"item","numeric-id":2294318,"id":"Q2294318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d8d76a1611561ef89e7637a7444628aaeacf340","datavalue":{"value":{"amount":"+0.859494686126709","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":"Q3002764$CFB30E5A-DF93-4B3F-926D-FB062CFD67E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b60674afd1bbdddfc75fbe9ced7c5a7aa41e82c7","datavalue":{"value":{"entity-type":"item","numeric-id":5172722,"id":"Q5172722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3325b23d88ac29539c604c6c7f15c85e293634fa","datavalue":{"value":{"amount":"+0.8054574728012085","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":"Q3002764$55FA1898-047F-4495-8CAB-4066B5DA1C46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"825b87fba54f68d17a58a15d20c962202d6923ab","datavalue":{"value":{"entity-type":"item","numeric-id":5219712,"id":"Q5219712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae7e13864f4f9137b9cf9a2eb16e4f9d34efff89","datavalue":{"value":{"amount":"+0.801207959651947","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":"Q3002764$8E3CCDAC-4879-423D-96BF-5D7ECF6C79D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"afc4ac075e24f22775a98f1de73679635471a973","datavalue":{"value":{"entity-type":"item","numeric-id":5390606,"id":"Q5390606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e252c479c3b1f3fdeee43cee32cad33c8dd3152","datavalue":{"value":{"amount":"+0.7996683120727539","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":"Q3002764$E98E40C1-9B51-403A-BAA9-2DDE45B871F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4accb0faa1d2fb257a56dd296495892ed6eea747","datavalue":{"value":{"entity-type":"item","numeric-id":5479373,"id":"Q5479373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c76399cbf81fc3f22efa8c477e91e8329bf6c14","datavalue":{"value":{"amount":"+0.7936201095581055","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":"Q3002764$58BB030B-E4DD-4493-8BD0-40E429CCDA36","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"6a554977dfac80e46d734f83d88900a7dc80a6ee","datavalue":{"value":{"entity-type":"item","numeric-id":6830589,"id":"Q6830589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3002764$983DC92E-DC7A-4A9C-A9C9-37925EE16969","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3002764","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3002764"}}}}}