{"entities":{"Q685520":{"pageid":687369,"ns":120,"title":"Item:Q685520","lastrevid":47189068,"modified":"2025-12-31T23:10:59Z","type":"item","id":"Q685520","labels":{"en":{"language":"en","value":"Approximating the minimum maximal independence number"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 417418"}},"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":"Q685520$70ED144F-8D9C-4300-A7DD-367B6E5A4CBB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c85a38f6da5d3054527ddf92d79f302f3cd21c36","datavalue":{"value":{"text":"Approximating the minimum maximal independence number","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685520$B7CEE258-F197-4E6E-94B0-CF3144EA45FC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"aed55910698a42f6f5c55f7dd37e48a8f4a5fc5c","datavalue":{"value":"0778.68041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685520$F5BC01F7-CC2A-4954-A178-5E615306A95E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8af3c43c96226ec755e5ed5762c9cf5404e1483d","datavalue":{"value":"10.1016/0020-0190(93)90022-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685520$0ED3C016-72F2-41AE-A6B0-2455C3303411","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"411282777dd6b69232cfefb6c570cb3fe6b91ce0","datavalue":{"value":{"entity-type":"item","numeric-id":235185,"id":"Q235185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685520$924BFEE5-5298-4304-8988-24A1F0D37DC4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685520$3BE88A8A-3EA8-4FCA-AB4C-C7172C67F671","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"729108c69527af72f2ca1b9041a9358219bdc1fc","datavalue":{"value":{"time":"+1994-01-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685520$0EF42322-91D2-4FAA-98D5-682422BB8864","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6967028675050702995c851c0765cd128b328a8f","datavalue":{"value":"We consider the problem of approximating the size of a minimum non- extendible independent set of a graph, also known as the minimum dominating independence number. We strengthen a result of \\textit{R. W. Irving} [Inf. Process. Lett. 37, No. 4, 197-200 (1991; Zbl 0713.68033)] to show that there is no constant \\(\\epsilon >0\\) for which this problem can be approximated within a factor on \\(n^{1-\\epsilon}\\) in polynomial time, unless \\(P=NP\\). This is the strongest lower bound we are aware of for polynomial-time approximation of an unweighted \\(NP\\)-complete graph problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q685520$8BE523E0-9903-4129-AC6A-D0B5A3FBFBC8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685520$73442258-E719-4889-8E01-1BFD21DD50F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685520$A8F9B3C5-756E-461D-BD5C-EBE79BC30313","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b5361e6f5026f2a68f46142b42243fc44b3a2778","datavalue":{"value":"417418","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685520$353B43D1-2569-4BFD-AD4E-B1E829169ABC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q685520$6FD9213D-2665-4A2D-B8C1-E42D26161421","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f2a62ef0b7b726291d9c31cc134c14354121a923","datavalue":{"value":"unweighted \\(NP\\)-complete graph problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q685520$39D01D92-7D3F-485E-9EE4-FD123F1647C1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"01b0989d65d3fe37f1a608a8cd96e416bda56c38","datavalue":{"value":{"entity-type":"item","numeric-id":200913,"id":"Q200913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685520$0494A834-A9FF-4509-AF6C-D1CDB5166E8B","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":"Q685520$ACD02733-DAE9-411E-AEE4-B99F8C631E1D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3191dda4a0c8fe0d15b2d491ec71326293311753","datavalue":{"value":"https://doi.org/10.1016/0020-0190(93)90022-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q685520$8C202F2E-AC54-4BF3-B001-B2B724B9D1ED","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"71ac6fc12e9026ed549759a6d7986f18b85dcd5f","datavalue":{"value":"W1976422444","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685520$FDEEE556-159B-4134-BACE-E6AD624B58E4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7258962f550bf808b8ce0edfe0f9b2099a09d076","datavalue":{"value":{"entity-type":"item","numeric-id":4230322,"id":"Q4230322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685520$05059A69-E666-4604-B03C-3211F5E5DD4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2be894136bbddcd6009199eaf9e6862c68de70b3","datavalue":{"value":{"entity-type":"item","numeric-id":750159,"id":"Q750159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685520$B26B86B1-63EC-4561-8F76-92A4B10E651E","rank":"normal"}],"P1643":[{"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":"d50f303d41329b10fa02566a7721cdc46f2dd92f","datavalue":{"value":{"amount":"+0.8805041909217834","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":"Q685520$4ABD056E-9FB8-40FE-939C-16394B19DA99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26205a3c58a5fc53d7580c2f4d67390629ba60fd","datavalue":{"value":{"entity-type":"item","numeric-id":1303785,"id":"Q1303785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd6328bf41a22dcab9438547da8a27a8c8b48aaa","datavalue":{"value":{"amount":"+0.8433025479316711","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":"Q685520$017A7FF1-AB69-408D-9D75-5A9482095FB9","rank":"normal"},{"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":"b2f9ce4d6bb6ebb787ee05070fabdbf9c11846d2","datavalue":{"value":{"amount":"+0.8346424698829651","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":"Q685520$C35F4C0E-76BF-432D-AB9F-2123B4E4C517","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"480e93ccc77ce1e3a314993cbcd6ad9bae9c9180","datavalue":{"value":{"entity-type":"item","numeric-id":2369972,"id":"Q2369972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2a8262e35b2ebaf214378d270b699a53e69da8e","datavalue":{"value":{"amount":"+0.8339537382125854","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":"Q685520$AEDF444A-5C80-49FA-829E-E9A41D879DF4","rank":"normal"},{"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":"8b30a137c98338882fe1f237e0d49b9028332593","datavalue":{"value":{"amount":"+0.8121469616889954","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":"Q685520$9D3D3A13-1FA0-4B9F-B05D-261F66D20DB8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:685520","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:685520"}}}}}