{"entities":{"Q1356067":{"pageid":1366806,"ns":120,"title":"Item:Q1356067","lastrevid":46547259,"modified":"2025-12-25T00:26:34Z","type":"item","id":"Q1356067","labels":{"en":{"language":"en","value":"The approximability behaviour of some combinatorial problems with respect to the approximability of a class of maximum independent set problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1016869"}},"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":"Q1356067$4CD1796D-B470-4DD4-BDF3-24F023F42679","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7dbf0ffa5a5b04d8aac01d9c865a9b510fe28da3","datavalue":{"value":{"text":"The approximability behaviour of some combinatorial problems with respect to the approximability of a class of maximum independent set problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1356067$283554E4-63A4-4211-87EE-952E7DFB34F9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3074cb385e8919bcd690fbf55083d1752b418a4f","datavalue":{"value":"0872.90106","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356067$E16E9824-A79A-42AE-926D-907004F4C28E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"daf1022abec3959c620199538bed8bbb504e8561","datavalue":{"value":"10.1023/A:1008660812834","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356067$EB9D68B8-331F-49A0-98A8-5AE5B0D38459","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"93f60862d1a3bdd4fb6752d0eea731ac1b19d5e3","datavalue":{"value":{"entity-type":"item","numeric-id":266807,"id":"Q266807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356067$B7891D34-CA08-4045-9A60-14200C0657D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"704cea475e2d3cbf7f9b1e09c1add901045357ec","datavalue":{"value":{"entity-type":"item","numeric-id":218830,"id":"Q218830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356067$75B1653D-16AE-43AB-A040-0E32A211AD91","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e8d56971ac7a9aaa935e275dc4574bf8a24cb87d","datavalue":{"value":{"entity-type":"item","numeric-id":174575,"id":"Q174575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356067$AF17C203-1DEB-4F27-BCA8-182887150422","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b9e3547502bf16346b2aff497a04c73350716529","datavalue":{"value":{"time":"+1997-06-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1356067$FF2338C0-6956-47D8-9051-6E912A9DE2FB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356067$991D0B22-EFE1-49EF-8369-0B7A946ABCC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356067$2492C056-DE33-4213-B199-19190DBFCECD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356067$17BCC070-E084-464D-BB00-48CEA241C8AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356067$E6A8C544-D120-4DE2-9215-2D367F28FAE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ccd1dd4cefa81e8158b9f080486a4eaed61a9ee8","datavalue":{"value":"90C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356067$415E3BEB-C9C3-4222-B2D5-61AD47707D02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4d4b880941bb65ec306ce9d3141ff7e82566f56","datavalue":{"value":"90C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356067$80F2AF38-F354-48AF-907C-FAA35E729519","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"97d1bdf196143124630b3bc10ee2ea1114031679","datavalue":{"value":"1016869","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356067$CC80B3C7-2AD4-41F3-9DD8-25136539D680","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50dc5a1d041f9e444212e60e5236dde69d229f7d","datavalue":{"value":"NP-complete problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356067$DD901FC4-75A4-430B-9B5F-7D68298FBEFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356067$8B43419F-99D1-444E-BE5B-4B07098D7003","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5e7bb40906f3791d7a5d3bc2bf8bbbd7f0b4657","datavalue":{"value":"polynomial time \\(\\rho\\)-approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356067$8CDBBF16-5363-462A-AA95-458CC5024C08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"95315580a488697753f314bcf92d6e8b4a36f135","datavalue":{"value":"vertex covering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356067$48B16F39-C112-449E-B699-3C5963A78FD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9c860dc7c11e0e802a7647d9cca3f8314a6a640","datavalue":{"value":"quadratic programming as subproblem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356067$CDA8BB4A-C0A7-403E-8E5F-76016FFA238E","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":"Q1356067$03331016-9236-47EE-82A7-07AB8E29A0E1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1ad07f8efd5929cafc739f04fb27016e397a6068","datavalue":{"value":"https://doi.org/10.1023/a:1008660812834","type":"string"},"datatype":"url"},"type":"statement","id":"Q1356067$46CD0E1C-3111-4D21-AA3E-02F2606F8327","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a8cb64989015e5cd5a52b6f6e89e0188eab4d635","datavalue":{"value":"W1539745397","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356067$36B4DD17-3D89-4FFC-8771-389CFF3E0505","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"629e72efedc441ea9946597f414efe4f6a003e14","datavalue":{"value":{"entity-type":"item","numeric-id":4864343,"id":"Q4864343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54eab29db19da4cfe592496e3280e28035657a26","datavalue":{"value":{"amount":"+0.8798856139183044","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":"Q1356067$E0BCFEA0-312E-474C-B5A1-E6E70C25E290","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2cacf6de452d99a2b85bde16aa2229639692604","datavalue":{"value":{"entity-type":"item","numeric-id":4887135,"id":"Q4887135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c23bf3e580c5bceaa851611619a13d283d45c7b1","datavalue":{"value":{"amount":"+0.8382603526115417","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":"Q1356067$408B633D-1859-41BD-802F-54A80FA31757","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"272ec1bd3d7c3f43750121e4027a3092397196e4","datavalue":{"value":{"entity-type":"item","numeric-id":760210,"id":"Q760210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5f5df5c893de8be0d4a51368587396968e25b40","datavalue":{"value":{"amount":"+0.8316939473152161","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":"Q1356067$1218AD25-C1E4-4B8D-9E7F-3E9017A89E5F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1356067","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1356067"}}}}}