{"entities":{"Q5269824":{"pageid":7299399,"ns":120,"title":"Item:Q5269824","lastrevid":52838594,"modified":"2026-01-23T15:02:38Z","type":"item","id":"Q5269824","labels":{"en":{"language":"en","value":"Nearly optimal NP-hardness of unique coverage"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6736409"}},"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":"Q5269824$196240D9-DA32-4033-8B28-7EE8C99C7E3C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"65ce6082f0adb0895394f25bf6a6a7467e6ef9a5","datavalue":{"value":{"text":"Nearly Optimal NP-Hardness of Unique Coverage","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5269824$2BE8C928-181A-41C2-B65E-7E670C46AB5B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"51f0b610e27247e1c4e86c6c647757f6750681df","datavalue":{"value":"1371.68098","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5269824$095E0EA3-1F4D-42A1-818D-D8C8544850D3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"39c3d9d2e3183d54702ded46dd71c3ed5696dc22","datavalue":{"value":"10.1137/16M1070682","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5269824$C6EA51DF-02EA-4375-A5B6-3A624E31856D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4da5d9d00c29a1438e24839583d2fe7db0d0793a","datavalue":{"value":{"entity-type":"item","numeric-id":315528,"id":"Q315528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5269824$69F6594C-A8B9-4EC0-9974-F28F9FFA8CFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7c036cc59d8136b1c1d330e12aacdea4899ce840","datavalue":{"value":{"entity-type":"item","numeric-id":293456,"id":"Q293456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5269824$1F9F726F-C5C6-4715-9A46-061A16859F7E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c2a1c45d0f0997786c62faf9f7fcd603424632e8","datavalue":{"value":{"entity-type":"item","numeric-id":84798,"id":"Q84798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5269824$42DC439C-7737-4012-80AE-9272467635C9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e1999ca064d94aea6a3057d7e34abd37331d8c09","datavalue":{"value":{"time":"+2017-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":"Q5269824$CD8A6290-9AE3-47CC-97B2-E592D6FBB185","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5269824$D2BFEF9F-1439-4DE0-8AF7-1D46A4CDAB58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5269824$74864882-CC2F-4BA1-BEFD-3612FAFF12BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5269824$88A9250A-58DB-4C69-8FAB-E381D63A421C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"307574edb5ca449b5ff2a3ee79b069f6ee2e48e8","datavalue":{"value":"6736409","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5269824$8A69A8C9-DC30-44B5-8FE6-6D7F995083A2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c932864c8d857b058190f9c7572ffef7f1e96210","datavalue":{"value":"hardness of approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q5269824$5F54BF3C-6B06-4B53-98E3-CF55038CE3C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac88b2a41a81d85de410e1d8d19c4e8d8c297e1a","datavalue":{"value":"unique coverage","type":"string"},"datatype":"string"},"type":"statement","id":"Q5269824$901200AB-D60D-46D5-97DD-3F87A0399371","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63f75b34f048fcf6a44b8a7a602f4e5ad02d0e71","datavalue":{"value":"1-in-\\(k\\) hitting set","type":"string"},"datatype":"string"},"type":"statement","id":"Q5269824$75E45FDE-EFD2-4EA1-A15B-668F7C3E1CCA","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":"Q5269824$ABE8E515-789C-4B0F-B7F1-817903051AEE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8563dbd2a86abf1770a68852886786fae93fa73","datavalue":{"value":{"entity-type":"item","numeric-id":3167386,"id":"Q3167386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5269824$38B4EE50-DDBA-4F5C-B795-E69000D67D77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"583011250710bd556ec11e3dcc35ec0d6e12e11d","datavalue":{"value":{"entity-type":"item","numeric-id":3395040,"id":"Q3395040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5269824$BE8B6BE1-E0B0-4395-958D-3E93EDC7299C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"783f5b77f65178466163307ca17329fb72140e4a","datavalue":{"value":{"entity-type":"item","numeric-id":3158517,"id":"Q3158517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5269824$1DB8686A-7D38-4D8B-8FED-26F9D29F82EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a157b93c6843fb22f2ec11d758cfb4e2cce5cee","datavalue":{"value":{"entity-type":"item","numeric-id":3579211,"id":"Q3579211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5269824$F8A6E2B0-9AB9-41C0-9AA7-8CE1D3888CEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9288e4395536915d083b24fca135b03bbfb84dd","datavalue":{"value":{"entity-type":"item","numeric-id":5269824,"id":"Q5269824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5269824$A5052976-1A4B-4927-A502-B7430E3058B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bc142b6db4b33c00813b975038092d8ee7337ce","datavalue":{"value":{"entity-type":"item","numeric-id":5479362,"id":"Q5479362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5269824$C0F79B8C-59D8-4996-9C14-7A5694EED2EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d672b7463e8a402e59b3fecf0e37e862728d0eb6","datavalue":{"value":{"entity-type":"item","numeric-id":2913811,"id":"Q2913811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5269824$2E9F0464-5DB6-4227-8B41-629F4DF349CC","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":"Q5269824$022AE9F7-77D1-4718-B101-9FE14B17ABCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24470a0a944fbaf9ee6181fbc49b02a7037f9ed6","datavalue":{"value":{"entity-type":"item","numeric-id":5757457,"id":"Q5757457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5269824$464B0470-43DA-42FE-8378-C1F7CEA7B1C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e956899ee0a7e06c94f20261b5948e49f9acb5d8","datavalue":{"value":{"entity-type":"item","numeric-id":4323730,"id":"Q4323730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5269824$CBAA2B9D-99A2-432B-87A5-3D0F4B997D88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fac33fcaba991f9403b8d09b8ef4fc791c0a07e","datavalue":{"value":{"entity-type":"item","numeric-id":3549708,"id":"Q3549708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5269824$A2694318-E4DE-4AA9-9145-F8FAA892DFAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3b8968dfdc94f8e24c739a40c68db87afaffdb9","datavalue":{"value":{"entity-type":"item","numeric-id":3191593,"id":"Q3191593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5269824$6D784516-34E5-471A-BDFB-F143B5F54EAA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6e49f51b6e36ddd10d092bf75a28e55334ef7666","datavalue":{"value":"https://doi.org/10.1137/16m1070682","type":"string"},"datatype":"url"},"type":"statement","id":"Q5269824$E835C142-631A-4B16-B4E6-8E352EBF42CE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"62a6a82135b4f71ee67be44b311da8b063b4f8b9","datavalue":{"value":"W2625369867","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5269824$BDC7F728-79EF-4B77-A0EB-6EDE64AB6C14","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06f3d4886421d3921ca1050dd661e3044ebb1a31","datavalue":{"value":{"entity-type":"item","numeric-id":4575703,"id":"Q4575703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca5dada81537a3c976f6cce704c3dc216fb41277","datavalue":{"value":{"amount":"+0.997859001159668","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":"Q5269824$221A8BBF-CA2D-49F3-9281-BC3AA25C4CD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c14c03b22a4d38c82f774981e665d53882bc3dd","datavalue":{"value":{"entity-type":"item","numeric-id":3395040,"id":"Q3395040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"364d863d11277a10478a82455ae5774223351546","datavalue":{"value":{"amount":"+0.843864381313324","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":"Q5269824$58A5B34B-BADD-48DF-88FA-9D40D9B7A87B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ccae982c765816dfae5525e0538860bcae96f2e4","datavalue":{"value":{"entity-type":"item","numeric-id":2754182,"id":"Q2754182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"beec74f1c5da53c787262cbc29f80f53a2537252","datavalue":{"value":{"amount":"+0.8004226684570312","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":"Q5269824$871F2FF6-A325-4419-BE2D-882F338FCCE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a39d1f219a9a19a8a8f3ad1c5c5c6a751d6f1726","datavalue":{"value":{"entity-type":"item","numeric-id":3088105,"id":"Q3088105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"beec74f1c5da53c787262cbc29f80f53a2537252","datavalue":{"value":{"amount":"+0.8004226684570312","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":"Q5269824$6D160D40-3F69-4468-80C7-62E2DC80574A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bca3329628da2155517baed4ce0504261eeb169f","datavalue":{"value":{"entity-type":"item","numeric-id":3158517,"id":"Q3158517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ebe1421b4571cadbd1ef4c0e3eb479075150756f","datavalue":{"value":{"amount":"+0.7935031056404114","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":"Q5269824$5FEE5E0C-9847-4295-B948-A15A8D9C40C8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5269824","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5269824"}}}}}