{"entities":{"Q760210":{"pageid":762059,"ns":120,"title":"Item:Q760210","lastrevid":48768148,"modified":"2026-01-05T19:53:34Z","type":"item","id":"Q760210","labels":{"en":{"language":"en","value":"On approximation problems related to the independent set and vertex cover problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3883606"}},"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":"Q760210$27F68671-B2D5-43A6-B3CC-2873D4D595F6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"25794be33e9f1fbb6b65818cf22a0a740b223c91","datavalue":{"value":{"text":"On approximation problems related to the independent set and vertex cover problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q760210$17378314-ECD3-4C6F-9F40-A074B246E3D9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5dc0f010840385e0c7f86e275b00d56eef59dfdd","datavalue":{"value":"0554.68026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760210$7777C9DC-E66F-43B6-9FBC-54FFD30E29FC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"11a83ddb654eb4a195ddf2373628b939a93009d2","datavalue":{"value":"10.1016/0166-218X(84)90086-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760210$E912DBB7-ACE6-4AAC-9A83-B42834F57ED6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760210$A0BAB8AB-EEA8-4DE0-A84B-96214E1822A1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q760210$5280AF7A-3229-4387-8D51-11A809E07136","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9dcddf4989d4488ebed697e8e28941a892e87ff5","datavalue":{"value":"Some open questions concerning the complexity of approximation algorithms for the Maximum Independent Set and Minimum Vertex Cover Problems are studied. It is shown that those questions are at least as hard as a sample of other open questions concerning approximating NP-hard problems, including Graph Coloring, Set Covering and Dominating Set Problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q760210$04BC82A4-C44A-48E4-B8CE-5BBFC61F867D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760210$4D3918AC-8377-4BDF-85C8-6A820C1DB536","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760210$C8E59501-1DFA-4818-AA9E-EBDD0EDF5C46","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ee1312284d39f8f28724219c6519a6a454a384f4","datavalue":{"value":"3883606","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760210$49B5220E-41E2-4064-9925-65CF10E259AF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"913667ea2b5e8bda2c707bf2cd507bf4b6d7aadb","datavalue":{"value":"complexity of approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q760210$7D9441CA-29B1-4A0A-8D97-1D696DD85AC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b5c5a416645e6119b32f5b21675ba4fed533e5b6","datavalue":{"value":"Maximum Independent Set","type":"string"},"datatype":"string"},"type":"statement","id":"Q760210$62348A64-2C9E-4705-A21B-4AF532AF4ED9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"12d0310797cdc676ce8186d2969f1810551167c8","datavalue":{"value":"Minimum Vertex Cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q760210$CFCFA12A-B779-4316-96CA-1C7005B8F661","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"91cc9aff8aea71118d3c150b25b82597f27b210a","datavalue":{"value":{"entity-type":"item","numeric-id":1130167,"id":"Q1130167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760210$69E01FA6-1AF2-49CB-BB4A-69B88FE72F7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3bd4342967813d6c73138a0b6a4a791b0a8c6593","datavalue":{"value":{"entity-type":"item","numeric-id":287984,"id":"Q287984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760210$CA015021-93EB-4E60-9C85-557F414B3E05","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":"Q760210$A2AA69F7-B38E-4963-94D7-165360501DE9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0411a384efe8f871835c9d52a082ddc67162974","datavalue":{"value":{"entity-type":"item","numeric-id":3910012,"id":"Q3910012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760210$0D4C1264-AB93-4B18-9144-6E6AC6E267E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"264cd15f78b9795d676e715dfd2e735f58fc18b5","datavalue":{"value":{"entity-type":"item","numeric-id":3221758,"id":"Q3221758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760210$97D9E016-A618-4232-A534-E93D6B7E95B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"633c232fef2c726e16f4745618f8111545145ff0","datavalue":{"value":{"entity-type":"item","numeric-id":760210,"id":"Q760210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760210$860E598B-5ADA-4216-A9CF-7D97CB909B46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd81f26dd5a6ed5fdca8ef33d505ef7f45a19114","datavalue":{"value":{"entity-type":"item","numeric-id":3933762,"id":"Q3933762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760210$46BE0C9B-FDF3-4D6F-B6BA-ACBB87249E70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a80eed9f379f185c9ca92aab1fa2ad3cc4463c9","datavalue":{"value":{"entity-type":"item","numeric-id":3887227,"id":"Q3887227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760210$F3EA8B3C-C1CD-49A3-8A39-19721299625B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cb6d330b0ba17ea9706ff485bd2cc7e5caf6771","datavalue":{"value":{"entity-type":"item","numeric-id":3883524,"id":"Q3883524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760210$701C35B3-D002-4D89-BD6B-B51968A20A2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc4f0630ec86e5a0d3e96a9ce7ec4c2915d07620","datavalue":{"value":{"entity-type":"item","numeric-id":4083458,"id":"Q4083458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760210$B63159AD-47EC-46A8-A5BA-1AB8C38C136E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e7d3dffde4b639a5080d558096cb7a34be71d72","datavalue":{"value":{"entity-type":"item","numeric-id":4146529,"id":"Q4146529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760210$1CBB18C3-7CDE-4B3A-B75F-05404CCE197A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760210$CD61F82B-AEFC-4E4A-A2CE-0F5D07A4AB6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00a9e252dcd967174efec124226bbf4f16c443d8","datavalue":{"value":{"entity-type":"item","numeric-id":3947140,"id":"Q3947140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760210$D0FA7A18-DC83-43DE-8363-D388FF104F75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a567a0bd5149009c58baa277d371437f0fed769","datavalue":{"value":{"entity-type":"item","numeric-id":1213733,"id":"Q1213733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760210$8B9766C2-E5BD-4D9D-B5A3-3E89924A44E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94d4ff0ae86125fc073ba1153e5f029193cd4ff2","datavalue":{"value":{"entity-type":"item","numeric-id":4065570,"id":"Q4065570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760210$519DFE31-3339-4BAE-8688-02AC332BA647","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760210$59FA7285-03CB-4D5F-BAF4-B1549AEA4B94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c2a0983ce7a664c54ed4274f83ecbe33679a4f0","datavalue":{"value":{"entity-type":"item","numeric-id":4074668,"id":"Q4074668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760210$67E3261C-D333-42FB-8B70-CC6D83B249AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df707866d55069e9c624e86b2f3ac5960ac5212d","datavalue":{"value":{"entity-type":"item","numeric-id":1152215,"id":"Q1152215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760210$F0415F30-6980-43CA-997F-367A03C0DC6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0669e594826b5b3523dfa03abf605c0d6353cb8a","datavalue":{"value":{"entity-type":"item","numeric-id":1171390,"id":"Q1171390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760210$28CF1E68-4BAF-4FBD-B9E0-FA844969FE56","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe7bd5af87bfc216857cc3aff614d41d4e397acd","datavalue":{"value":{"entity-type":"item","numeric-id":1184733,"id":"Q1184733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dda77a41decdd8e3d0c94ba6b169a1849064bfeb","datavalue":{"value":{"amount":"+0.8332903981208801","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":"Q760210$86D813EE-4558-4073-A860-B77B92B70B1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2786f2a6a45dbd1b972df579ad4aee824a0963a","datavalue":{"value":{"entity-type":"item","numeric-id":411835,"id":"Q411835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0259dde990b6fb3be0a73a264a8b82d1443fbc5","datavalue":{"value":{"amount":"+0.8327471017837524","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":"Q760210$777A8DC9-ED33-4276-842A-1543855D26A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"228d89a139322a390eb7a42766e37e5b6c3fee3c","datavalue":{"value":{"entity-type":"item","numeric-id":816330,"id":"Q816330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5d1272bfe06ce4f14217ba9c04557fde095955f","datavalue":{"value":{"amount":"+0.8326666951179504","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":"Q760210$E3CE05C1-04D7-4D24-8E03-3A883DE94AF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4d0a720b31fb830b72f88f16e58d9a48703aaa0","datavalue":{"value":{"entity-type":"item","numeric-id":1356067,"id":"Q1356067"},"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":"Q760210$5D585846-91B8-44CF-8D13-5B11B8D1B15C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91180eda8f021b1a5a7116dcf1d980fd22e7f02f","datavalue":{"value":{"entity-type":"item","numeric-id":4323730,"id":"Q4323730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a8fd9d74e79b53d79e4c36911a2f4ef652b1c83","datavalue":{"value":{"amount":"+0.8185615539550781","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":"Q760210$1A4EB1C7-98A9-4D61-9A70-7F8170762819","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:760210","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:760210"}}}}}