{"entities":{"Q1184733":{"pageid":1195482,"ns":120,"title":"Item:Q1184733","lastrevid":66791955,"modified":"2026-04-12T12:53:13Z","type":"item","id":"Q1184733","labels":{"en":{"language":"en","value":"On the complexity of approximating the independent set problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 34932"}},"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":"Q1184733$75078401-17E2-483A-8124-965E3505E3E4","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":"Q1184733$BDD84928-32AF-45C9-9ABA-AC2839F81155","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2ccf5003da903a9cfb6cc39030c39080a69218ca","datavalue":{"value":"0804.90121","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184733$D2BE3F17-A887-4A7F-A8EF-06364452328D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bb9eb078f19e0c7799fe14f82ae8ca7966b3ea0e","datavalue":{"value":"10.1016/0890-5401(92)90056-L","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184733$051EDEA0-3A61-42B5-9415-8979D4FAADDA","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":"Q1184733$0F0949CD-1F54-4BD3-A0E4-91B445388F52","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":"Q1184733$0A209383-4390-4A61-B779-E68F26909B19","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184733$A5AB7C7C-6361-424D-BED3-78D72EA39261","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1184733$5F15BB87-66A5-4E80-BF35-DCBBC5D3FF49","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c1cbbbed58189098adf9acd6c2518e4ac733dd37","datavalue":{"value":"It is shown that for some positive constant \\(c\\) it is not feasible to approximate the independent set (for graphs of \\(n\\) vertices) within a factor of \\(n^ c\\), provided maximum 2-satisfiability does not have a randomized polynomial time approximation scheme. Reductions preserving the quality of approximations are also studied and complete problems are exhibited.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1184733$953B48AC-7BDF-4F70-B247-FAA21A716E4E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184733$7FC01269-6650-4503-81D6-343487D9ECC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184733$255DE794-9051-41D5-803A-6C901772169D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184733$AC6ED8D9-CFDD-420F-9D2A-8BBEB0269F32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184733$4570FF52-B1F2-4347-A7A4-EB1677544378","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7c9b559533ea7a2af2366000053e5ff45458ba57","datavalue":{"value":"34932","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184733$38AAF96B-E008-42FA-B0E7-5ED7D63BB885","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1184733$739550BC-8FD1-4BE9-921D-3D46E5212C14","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":"Q1184733$763EF712-ACC8-40C0-91D9-B70F276CA74A","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":"Q1184733$B6E9F961-25BD-4437-86A5-BADDF4142861","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":"Q1184733$A5D92FB0-E16A-455E-9B0D-78EEEFE7ECF3","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":"Q1184733$F0929C86-B490-4DD9-8634-14139DAB64D3","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":"Q1184733$CB1CB65C-8F84-4A73-B42E-4BCF53ECA212","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":"Q1184733$0FB82BD0-446F-4912-945E-D886F683A5E7","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":"Q1184733$8577E2FF-E6BC-4979-990C-54E454359CCA","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":"Q1184733$D8E7490B-C433-4FA5-946C-BBED75A4E5E6","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":"Q1184733$C1FB4A5C-E729-46F3-8CC6-FEE9CD625E3F","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":"Q1184733$5506A84F-EC3B-4C00-920B-60F85CDDDA11","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":"Q1184733$D90F55F0-713E-4EF2-8899-F0954A31D77C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09648e052a17cba3423c34ac324f13603f8af64f","datavalue":{"value":{"entity-type":"item","numeric-id":3867858,"id":"Q3867858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184733$348647A0-93DA-4024-9C09-0CFFDF50EE53","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":"Q1184733$F614BAF3-F7AB-4A83-9DDA-61CDFFE43C03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aecbfbe764c73b405203223e4c4ac2dee201dd0b","datavalue":{"value":{"entity-type":"item","numeric-id":3338254,"id":"Q3338254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184733$E505BC59-E3D0-4D57-85A0-F1191EE1D0EC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1240521626704a5a12f2375bb90070c042192f2c","datavalue":{"value":"https://doi.org/10.1016/0890-5401(92)90056-l","type":"string"},"datatype":"url"},"type":"statement","id":"Q1184733$FA1722BC-8A98-4BA2-9F04-382A2C207A1C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fc8b18eaef5955cfdf083be504edabed950c09e0","datavalue":{"value":"W2053651631","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184733$D27F0BFB-3540-4E6C-B590-B4EC219FE627","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd51551bc11c16b95911c40e84e8c0089b1131d3","datavalue":{"value":{"entity-type":"item","numeric-id":5096160,"id":"Q5096160"},"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":"Q1184733$6FEEF406-545B-4B1F-A359-7D68AF78087A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"141060f2e3ed11e3c1570c65949c62a7a7409123","datavalue":{"value":{"entity-type":"item","numeric-id":1281930,"id":"Q1281930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c54edc72d76c77f5bca878c07a5d0d470989ffc","datavalue":{"value":{"amount":"+0.8556071519851685","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":"Q1184733$BBB10F9A-5569-4885-9BC6-2B02EDF5246B","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":"239d16f3cf27009d39ff0a6e4fb310990005879c","datavalue":{"value":{"amount":"+0.8504979014396667","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":"Q1184733$C926660C-541C-49C2-AA30-2C7128738BA9","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":"37f8c616c7af3e86a3570caec3cef2d5b09e81e7","datavalue":{"value":{"amount":"+0.8493674397468567","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":"Q1184733$57C38EBD-FD2C-4076-86A2-5EB1736ED926","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0cd00109b43c121445260f4e4fb8cb7e7c0787cc","datavalue":{"value":{"entity-type":"item","numeric-id":685520,"id":"Q685520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e625abcd95a040932843582fdc2466e45d31b40","datavalue":{"value":{"amount":"+0.8461804986000061","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":"Q1184733$53C7B203-AD24-41EA-ABCA-11E3F17A441C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of approximating the independent set problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_complexity_of_approximating_the_independent_set_problem"}}}}}