{"entities":{"Q5096160":{"pageid":7125736,"ns":120,"title":"Item:Q5096160","lastrevid":94266455,"modified":"2026-06-05T06:22:58Z","type":"item","id":"Q5096160","labels":{"en":{"language":"en","value":"On the complexity of approximating the independent set problem (extended abstract)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7571933"}},"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":"Q5096160$BEB0F165-38AF-4025-A93D-8338ECEB96DA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"aa6604b0d9bdd57c8edf52620a08971f66726301","datavalue":{"value":{"text":"On the complexity of approximating the independent set problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5096160$8E35ED5B-99E5-4029-B5BE-6A2C9E3D18AA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e99c42374c8a9591afa746578e9785881ee366a3","datavalue":{"value":"1492.68060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5096160$6406D353-901D-4C52-B949-17BB40FE873F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"544d0b7ba4444928caddd3ee5ebd1b425c121444","datavalue":{"value":{"entity-type":"item","numeric-id":397069,"id":"Q397069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5096160$74576345-E737-46B5-8458-19B266308871","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1ea84784d0ec02c56a3f38dfe8d621cdc682004f","datavalue":{"value":{"entity-type":"item","numeric-id":436320,"id":"Q436320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5096160$7ED62924-4E71-43B5-AC23-A68FF8FED937","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b060475a421a23318c909b1beea7e63f4d8ea20e","datavalue":{"value":{"entity-type":"item","numeric-id":5096138,"id":"Q5096138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5096160$4D37069F-33E8-4896-BC22-5D6A4ACFE78C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9f0638de14cb053deb57828797f5c127a478dbaa","datavalue":{"value":{"time":"+2022-08-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5096160$B9441F1E-A5F8-46AE-95F9-CFF44B5A5848","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5096160$EDA0D72B-2602-4EA7-9C6E-2D3B792313A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5096160$0D856C8F-2DDD-4181-897E-7B5208C2577E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5096160$3A1D0CFA-C5BB-497D-83A0-5FAE37D70AA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5096160$03DACD95-8139-499E-836E-30263F262E32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5096160$807BA297-E1FE-4833-B159-51C3D5093327","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7b9532234deb17784cf2f95b3e5543bf16f85c2a","datavalue":{"value":"7571933","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5096160$413DDD07-19CB-4CCE-8524-73744FBBDF9B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bbd038c71261374a180387848563794446290f02","datavalue":{"value":"feasible solution","type":"string"},"datatype":"string"},"type":"statement","id":"Q5096160$08FCF0E1-96A7-4913-883A-DAADC1522CE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q5096160$D689E772-C049-414E-882B-6F791DA981F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3fd8de89e277c945b9e4dcef50b5e00b0399783a","datavalue":{"value":"maximization problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q5096160$C091C88A-1D96-4153-9F4E-EBFC4285AF43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0343095f51ee5e2d8c3d30f6658caa53e8a649e2","datavalue":{"value":"combinatorial optimization problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q5096160$45ABE909-B63B-4C27-B175-862F1796FE48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"600c1e6cd816b63470df7d348a4275d1b81cf52a","datavalue":{"value":"polynomial-time approximation scheme","type":"string"},"datatype":"string"},"type":"statement","id":"Q5096160$88895249-8A0C-4EE0-A63C-6C0086B7EE7C","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":"Q5096160$69267042-4688-4549-9516-73C86F83C3BB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a69e32404e054db67ecfcb8f51c548a89f56c6d","datavalue":{"value":{"entity-type":"item","numeric-id":4133133,"id":"Q4133133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5096160$F855555F-0E45-4099-8A39-04E010988184","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9dc4dc8695aaa4d0ec31340b16f1901c662b5229","datavalue":{"value":{"entity-type":"item","numeric-id":1143173,"id":"Q1143173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5096160$9910A716-6154-450E-9926-768A766A4D61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ed5651e7c87d511d2ce0af1f61c3115ddbea240","datavalue":{"value":{"entity-type":"item","numeric-id":1143789,"id":"Q1143789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5096160$B0910858-E546-4162-AFF3-080B4E178A3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77d6452e54e5e6983bfa6dba10e55824db2fd929","datavalue":{"value":{"entity-type":"item","numeric-id":5814290,"id":"Q5814290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5096160$90C0820B-0F9B-4987-8EA1-8C99357156C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"631afda92da774b2f35528b579855e622332ed35","datavalue":{"value":{"entity-type":"item","numeric-id":4065548,"id":"Q4065548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5096160$EA1FEC03-740C-4EA2-81B8-E46BB7147232","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9539532d16bcb82516fae2db58a1eb7e9c6ca7b","datavalue":{"value":{"entity-type":"item","numeric-id":5538132,"id":"Q5538132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5096160$BB54E17A-6E2A-4941-8361-BDBD7DB0986C","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":"Q5096160$E15C99CF-6F6B-4876-AB9C-104C45EE452F","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":"Q5096160$A04F5E2A-93D6-46F5-AFD7-EB20348108CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"659cdaa15ad6d89ec32129a4bed8372f5f89fdf6","datavalue":{"value":{"entity-type":"item","numeric-id":4147591,"id":"Q4147591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5096160$03C0E982-E7DA-4838-A9C1-DA2F5501B763","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85b870ff096cd9b7374b71a9c8fe8f62feec4207","datavalue":{"value":{"entity-type":"item","numeric-id":3219752,"id":"Q3219752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5096160$B4395C06-12DE-4490-B078-7289C9AEDE81","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":"Q5096160$AB987201-E4DD-4FFC-8AF2-06BBEB54A210","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6a70ba069210f50eb3bb60fe7187457a27b389c2","datavalue":{"value":"https://doi.org/10.1007/bfb0028990","type":"string"},"datatype":"url"},"type":"statement","id":"Q5096160$3540BEBB-ED2B-42FB-A5B5-E9A6B125AD91","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a48b407967711444fed7ac5cfa85af17432c0ff6","datavalue":{"value":"W1510300750","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5096160$22382384-9790-4DBC-AE48-CE8DADB6BB31","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"544b3d9d4830abb7b76c24fb07710f56d1378352","datavalue":{"value":"10.1007/BFB0028990","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5096160$44F490F0-5F93-4868-A9E7-E325872B9C90","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":"999cddfb224eaf2dca96d63491f7358c05f0221d","datavalue":{"value":{"amount":"+0.983820617198944","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":"Q5096160$25AB718C-76E8-4D99-AC07-31C5B47A6583","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f5b3cd7a04ae04fdda6507f54fc702dd8e9cdf19","datavalue":{"value":{"entity-type":"item","numeric-id":750159,"id":"Q750159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4cb4785b4b6a839d0b814eea080a975d837e7198","datavalue":{"value":{"amount":"+0.9825869202613832","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":"Q5096160$B6BC25C8-98FC-4A93-A84A-BC80607CEFAF","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":"1f6ceb76af08a704f88071358c63238d81fe3aee","datavalue":{"value":{"amount":"+0.8301828503608704","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":"Q5096160$AB8BD2C8-6CD0-47E0-B9AB-1003A7A9F893","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c4a05baa18dbd14ee62eeaf49476a80214c3d07","datavalue":{"value":{"entity-type":"item","numeric-id":1183338,"id":"Q1183338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be812516f40856b0544a9bb712f6d8471a992ad9","datavalue":{"value":{"amount":"+0.8294429779052734","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":"Q5096160$C0F28130-0C62-4FED-A6C8-D7A86A7ABCC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c234b2dfaa15f5c402022f846a67cacb4825f44b","datavalue":{"value":{"entity-type":"item","numeric-id":5057456,"id":"Q5057456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a41ab81066b433f4c234f5280ecada669bdfa8d1","datavalue":{"value":{"amount":"+0.8251834511756897","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":"Q5096160$40E76449-2E30-4614-B8C6-E79292A2F774","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of approximating the independent set problem (extended abstract)","badges":[]}}}}}