{"entities":{"Q2475406":{"pageid":2486149,"ns":120,"title":"Item:Q2475406","lastrevid":50301275,"modified":"2026-01-13T19:05:21Z","type":"item","id":"Q2475406","labels":{"en":{"language":"en","value":"Vertex cover might be hard to approximate to within \\(2 - \\varepsilon \\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5246767"}},"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":"Q2475406$E170AEF6-2F77-42B6-A1F4-BFD31A25EAC9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1eac8a7d32c598fe099e852f8d77ab53b978db1a","datavalue":{"value":{"text":"Vertex cover might be hard to approximate to within \\(2 - \\varepsilon \\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2475406$51CFDF7E-E8CE-4713-B449-A0F41BCA5007","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d140259f5872f97b4357dfac63e626581068fed3","datavalue":{"value":"1133.68061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2475406$45100A80-C56C-42BE-A1E6-45C085D5DCE3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d9f6b5d26f49366977cda1349aa1fe24902e4163","datavalue":{"value":{"entity-type":"item","numeric-id":375694,"id":"Q375694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$360EAE20-A867-458D-BF7A-4B7B0F436E18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc0f476358ab3d9fa7f8c58db4d920df08a5d274","datavalue":{"value":{"entity-type":"item","numeric-id":430831,"id":"Q430831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$E75CA73C-05A2-425D-B80D-8195B15F0060","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$8CD688BA-C437-4D57-A4C9-5E8DB788B209","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c5191b06fb6cb88c011afaa0f154255cfe3a8de0","datavalue":{"value":{"time":"+2008-03-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2475406$95EF5969-C563-44D0-BF91-23978A07A10E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2475406$2BF95270-7FD9-488D-BEF8-DB4E25D5B552","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2475406$39F72CC0-EB7B-4792-8252-750C5BAE2230","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2475406$6658CC08-0D05-4E12-9AEE-3D8CD71998D2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5ba6d816834cf26bb1bbab3e55f5c48fadf13867","datavalue":{"value":"5246767","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2475406$FC3C6527-FE5C-4DB9-A334-C87C2DF1A316","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c932864c8d857b058190f9c7572ffef7f1e96210","datavalue":{"value":"hardness of approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2475406$87F3D923-22CA-4967-B979-47780D07B80F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aac385c43cc6d982a9dd1fbfee8ab2754a681c11","datavalue":{"value":"vertex cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q2475406$78671E3B-A326-4836-ADC3-F6419BC73B7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e088df1fc83158b6e99a19b8d624735c4cb0c49e","datavalue":{"value":"unique games conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q2475406$335D4950-AE61-4018-A0CD-DB0DEA2D93EA","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":"Q2475406$14C73B7D-D65F-42B5-B9D7-1C37CE235213","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a4c29860b3c64e6b5690dca2c60407a00e8bf189","datavalue":{"value":"https://doi.org/10.1016/j.jcss.2007.06.019","type":"string"},"datatype":"url"},"type":"statement","id":"Q2475406$0ED730E4-DE1A-4C49-AF27-3B7C2DDBCC96","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c7d19ac62ef4f45b15d1583f96ac90ba13d33945","datavalue":{"value":"W2137118456","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2475406$11101D6D-097A-40F6-B417-54ECBEF07704","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"5769d2a7ebb1ff6de27ec114c42df9eee1110ad3","datavalue":{"value":"Q94993767","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2475406$11864A45-843B-4247-B645-D6E774B79677","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed97d9cb381fa44bbd6ac9207fd7e4aa47354791","datavalue":{"value":{"entity-type":"item","numeric-id":3158513,"id":"Q3158513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$8AC8C3FC-58D7-48CC-84AE-C4F675F79905","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11f3a5a6ef5b4dad2d6e7e841bea784191d0a73c","datavalue":{"value":{"entity-type":"item","numeric-id":3841041,"id":"Q3841041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$065FF587-5FA9-4B52-8D75-0D610EA85E11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f8452767e48792d351acf5067c416d60a7b2b74","datavalue":{"value":{"entity-type":"item","numeric-id":4388899,"id":"Q4388899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$941A0D76-32A0-4913-B8F9-E5A6D9947475","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"210c71e61c629822f548ece6c4eda7b30cf33ca0","datavalue":{"value":{"entity-type":"item","numeric-id":2931385,"id":"Q2931385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$F1F843E6-E106-4588-B7D0-9E5D828630FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ffc0f37120c3fc43c2fea1a11a4e6eb759cdb9db","datavalue":{"value":{"entity-type":"item","numeric-id":2458939,"id":"Q2458939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$89EDFDD3-67D2-489E-88B4-87BB43E56376","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2fefa93a64939b38db387938c28d3e1c44c75632","datavalue":{"value":{"entity-type":"item","numeric-id":5317188,"id":"Q5317188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$3E3CFCFE-C2F7-469F-B3A9-DF1A4F3C2E38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92ae3938d617cdee249b8b63bf400c6abe6445ac","datavalue":{"value":{"entity-type":"item","numeric-id":2931398,"id":"Q2931398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$C06748F0-17D4-4ACA-9F7F-F094460B8482","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5bafed8482918a0ff74bcc7a2a71d3b2bbb5752a","datavalue":{"value":{"entity-type":"item","numeric-id":816330,"id":"Q816330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$B44FEE03-E44A-4A26-9842-395D44AF4A83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28da4ab3ef0330f2d27f75b51be7a849803967f3","datavalue":{"value":{"entity-type":"item","numeric-id":1280280,"id":"Q1280280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$6485465E-C86A-45E1-A0D4-C939B87806E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e45bf7d05ec2c63e215cf650bed2ac0d1855c6a","datavalue":{"value":{"entity-type":"item","numeric-id":3088179,"id":"Q3088179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$CF172D8C-7CDD-4103-9634-87388618996C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b47a85e408a0fb723871c99382c9ab02f7d8cef5","datavalue":{"value":{"entity-type":"item","numeric-id":3581527,"id":"Q3581527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$0C4A393A-EA32-4553-A551-42D1223E0594","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94b113ba05d56c89c3c4f8588892cdf5e27b18e3","datavalue":{"value":{"entity-type":"item","numeric-id":3149889,"id":"Q3149889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$EA9162FB-C699-4B41-9078-2EDC8A1BF376","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd40e76594a43720fae74f641ef5b271afa3c125","datavalue":{"value":{"entity-type":"item","numeric-id":3149886,"id":"Q3149886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$1177BE37-48B4-48FA-B91D-4DFCA3830383","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c837d56e04962823c1d7c934cd015e72d540d8c","datavalue":{"value":{"entity-type":"item","numeric-id":1588908,"id":"Q1588908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$D50C1711-7208-4A4C-9641-0AC1DF94C657","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63223a2b10e799e0a620d9698b0286ebd9668db5","datavalue":{"value":{"entity-type":"item","numeric-id":5441360,"id":"Q5441360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$AFA6DBEF-F7A4-4447-84D1-DABFFAB6DA32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5768a5a4aa263954964ccc2d46127cd6b7dfbe01","datavalue":{"value":{"entity-type":"item","numeric-id":4737227,"id":"Q4737227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$819F2D99-6B6A-4FAD-85C0-812CBFEB53EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ff63997efc279b7fd5f06f8f3e05b3ce552f57c","datavalue":{"value":{"entity-type":"item","numeric-id":3579212,"id":"Q3579212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$89DA6467-605A-4478-9E07-F0BC82B74C76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b58fad3b4ec3d547a24cb6c24802aad6e81000e4","datavalue":{"value":{"entity-type":"item","numeric-id":5716851,"id":"Q5716851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$F9C7A22A-D98A-4160-8D07-67711B854E7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e1a59b9106a5dd5105f2bc476300c4cdae45ec3","datavalue":{"value":{"entity-type":"item","numeric-id":3579218,"id":"Q3579218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$AA6D7593-8A6B-4F5E-A391-1BC9D31ADA91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"434e3d029b3c74ed7da0e93d488afceb7c5b2fa6","datavalue":{"value":{"entity-type":"item","numeric-id":5454254,"id":"Q5454254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$A4B07503-7C2D-427B-8F84-4FDB4D9933B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d93c4afbea634568a441363673422b65f9608f49","datavalue":{"value":{"entity-type":"item","numeric-id":5501953,"id":"Q5501953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$A705C951-7FB6-4847-B4E1-EC9B082E5EC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8644c306cb8a0d42c04c1869ac95c3c18c2307e5","datavalue":{"value":{"entity-type":"item","numeric-id":4083487,"id":"Q4083487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$861871B4-DB4B-4B38-9365-D575C625F9BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc7c1b8cc24016a7c6b464cd2135f72b919e9781","datavalue":{"value":{"entity-type":"item","numeric-id":4388898,"id":"Q4388898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$2DA18ACA-846D-406F-90AF-B2C14C0040CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b37d1e830ad1e3027640f0208406560240ad6501","datavalue":{"value":{"entity-type":"item","numeric-id":3966856,"id":"Q3966856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$6DF6E2CE-24AA-482D-8E1D-3FD79B4B3233","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b56424e433709278d351cffdfc61a38ea84ebbea","datavalue":{"value":{"entity-type":"item","numeric-id":5176001,"id":"Q5176001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475406$9BEBCC11-EE1F-4F55-99CF-F44D2D879C1B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"72b6bc532f2c34def39f4921c7300c0f8fbbdc80","datavalue":{"value":"10.1016/J.JCSS.2007.06.019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2475406$E3F2FFEF-B0BF-4452-9468-08B5F81F3CD2","rank":"normal"}],"P1643":[{"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":"2e3087ff66af201daa42eef225ac93c7c1f22aa1","datavalue":{"value":{"amount":"+0.898077666759491","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":"Q2475406$41313826-8CE7-4EAC-926C-6A98F6C10B69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e472d7b12e26f0699150640a3e400fdaa56d086","datavalue":{"value":{"entity-type":"item","numeric-id":4962765,"id":"Q4962765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd76621cc22330710d24df5c2abb49c11135fab2","datavalue":{"value":{"amount":"+0.8834156394004822","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":"Q2475406$80FC6ACE-8807-4BE4-A562-2B77AF0994C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ac357fe6b363a31bbac12e45a2bd98be5302c1f","datavalue":{"value":{"entity-type":"item","numeric-id":4737227,"id":"Q4737227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"711f97bc317c8cc3b309e3931d113ce277d77a11","datavalue":{"value":{"amount":"+0.8787269592285156","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":"Q2475406$D09FA4F0-9622-4EF8-8759-A68190E9B1D7","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":"755ac7330b0173b59df334844acdadfc8531a6e9","datavalue":{"value":{"amount":"+0.8708380460739136","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":"Q2475406$3BF9270A-A81D-4DD4-95F3-FE80D1330FAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b63363769cbd159cf35d207aba2fcaa169f903a","datavalue":{"value":{"entity-type":"item","numeric-id":3581279,"id":"Q3581279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c777cb55b35625c6fa24e744336cce273074af3c","datavalue":{"value":{"amount":"+0.8705083131790161","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":"Q2475406$F85F2A14-6BED-4655-A6E7-63CCEBDBCCC9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2475406","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2475406"}}}}}