{"entities":{"Q1765237":{"pageid":1775979,"ns":120,"title":"Item:Q1765237","lastrevid":72912867,"modified":"2026-04-14T08:43:24Z","type":"item","id":"Q1765237","labels":{"en":{"language":"en","value":"Optimal covering designs: complexity results and new bounds"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2137272"}},"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":"Q1765237$9F053483-AF1D-4152-B60C-94F84A2BE5BD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"343b746a323ee161cbe01183f9bdccff40f69ade","datavalue":{"value":{"text":"Optimal covering designs: complexity results and new bounds","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1765237$D8F52E74-E413-498E-BD38-4484951B5BC8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"14af3a5e94b58feb4165edb917fa689f12349564","datavalue":{"value":"1063.05031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1765237$822CCC0B-A78A-4103-BE7D-E715199F622B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fd242065b6c25f89241c83bdf45f84b76d2037a2","datavalue":{"value":{"entity-type":"item","numeric-id":456359,"id":"Q456359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1765237$9F33171E-895B-463F-BB81-8564383C6C3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0538be50839595013ad820ab0e1fecf2c0f5eff0","datavalue":{"value":{"entity-type":"item","numeric-id":899312,"id":"Q899312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1765237$E1ECE9DB-EAF3-4D84-85CA-90C1596E0024","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"91d50cdeb23e4905b247ff213c2d9fe1cf6c555a","datavalue":{"value":{"entity-type":"item","numeric-id":222483,"id":"Q222483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1765237$5287666F-904A-4DCA-83F6-B73A667DFF0E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1765237$E41902D9-CF9A-44BF-9608-C5F2E22536EF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0f8b72aeee9429c75f6d2c214b1fe1fedeb47fc2","datavalue":{"value":{"time":"+2005-02-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1765237$22E84478-4B45-428F-B856-DCE633444661","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f00270058a5f5821673ba7bb4e599d4e9f5c7722","datavalue":{"value":"A \\(t\\)-\\((v,m,k,\\lambda)\\) covering design is a subset \\(\\mathcal{C}\\) of the set of all \\(k\\)-subsets of a \\(v\\)-set \\(S\\), such that, for any \\(m\\)-subset \\(A\\) of \\(S\\), there are at least \\(\\lambda\\) elements of \\(\\mathcal{C}\\) which intersect \\(A\\) in at least \\(t\\) elements. The minimum cardinality of a \\(t\\)-\\((v,m,k,1)\\) covering design is denoted by \\(C(v,m,k,t)\\). The authors obtain some new upper bounds for \\(C(v,m,k,t)\\) for certain parameter values. They also consider the following variation of the problem. Given a subset \\(\\mathcal{T}\\) of the set of all \\(k\\)-subsets of a \\(v\\)-set \\(S\\), find a minimum cardinality subset \\(\\mathcal{C}\\) of \\(\\mathcal{T}\\) such that, for any set \\(A\\) in \\(\\mathcal{T}\\), there exists at least one set in \\(\\mathcal{C}\\) which intersects \\(A\\) in at least \\(t\\) elements. The authors prove that the computational complexity of this problem is \\(\\log{| \\mathcal{T}}| \\)-approximable and that it can not be approximated within a factor smaller than \\(\\log{| \\mathcal{T}| }\\), unless P = NP.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1765237$F9AD98F8-E53E-4E61-82CF-250F0C226DAC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2fd42e66b6fddca288d4376ed553a53a921b9ec3","datavalue":{"value":{"entity-type":"item","numeric-id":579264,"id":"Q579264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1765237$28133C2E-55F6-400D-B426-A87A7638BF62","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb6fa31c061028a10fb1c2a1679af7746583c504","datavalue":{"value":"05B40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1765237$E6D673C6-9835-4967-9D8F-73FC3BBA95E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5106252eb72617afc052c075699a4fbf786bbc66","datavalue":{"value":"05-02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1765237$683A3842-4BA5-41F1-98A9-DE4FA1267F79","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"405d12caa6fec7633691381b8edf905fec7b0046","datavalue":{"value":"2137272","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1765237$C877FC08-A2E2-428D-8E25-5F8308911C1C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"297c99fa044086ac44cb88bbfd3bd24a2c960d3b","datavalue":{"value":"optimal lottery scheme","type":"string"},"datatype":"string"},"type":"statement","id":"Q1765237$2312F409-2999-4B33-9ED2-A88FB8D7C2AC","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":"Q1765237$4C9EAE24-C673-4AB2-9E91-AD1B15CD34D9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e1bb167ab80cabb6ad5a79b66ba73bec97c055e6","datavalue":{"value":"https://doi.org/10.1016/j.dam.2003.11.006","type":"string"},"datatype":"url"},"type":"statement","id":"Q1765237$347EE891-1927-4C60-8532-2832A7076C33","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a95f2711e1b47ecdf8274763b00e98383341db93","datavalue":{"value":"W2044660400","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1765237$F8D3AF26-119A-4F0D-B2CA-E8C37B3E5FAD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5aa2a1ac4e864d41c30b8a828a68a91d18d8ecae","datavalue":{"value":{"entity-type":"item","numeric-id":4258216,"id":"Q4258216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1765237$61C83C72-7632-46F6-A735-C49D5980D937","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05b55115d0447ce9ecd72acf486b1857ab97e589","datavalue":{"value":{"entity-type":"item","numeric-id":3936754,"id":"Q3936754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1765237$466DA984-FF4C-4F11-AA48-17E0140D807C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b603d0f27ed88f45cd3b15514bf81515680bb0c","datavalue":{"value":{"entity-type":"item","numeric-id":1182924,"id":"Q1182924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1765237$A7DF1867-8C26-4FE4-8E5E-7E9316171BE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d37046fb589da84db83ecb86b78e2e2dbde8e586","datavalue":{"value":{"entity-type":"item","numeric-id":4764667,"id":"Q4764667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1765237$C98C465F-C8D8-444E-BF65-DCA876069AD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f3bd04e5122ae04deca2213c60a48fd4a4a3d35","datavalue":{"value":{"entity-type":"item","numeric-id":4373370,"id":"Q4373370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1765237$17E75FF1-9852-4508-81C1-3324E24793BB","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":"Q1765237$9115B2B5-7278-41AD-8F51-7F8EC9363BD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dad6c975498c7bec8a56393bbbb7e324e7dfd7fa","datavalue":{"value":{"entity-type":"item","numeric-id":762162,"id":"Q762162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1765237$DD383517-D3AC-4F7E-B078-1630A96BA48D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b32d523d22765d89f56d17bf67192a7980cf9837","datavalue":{"value":{"entity-type":"item","numeric-id":4026151,"id":"Q4026151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1765237$8ACF99A1-5663-49F5-A0B3-0C96A888CEFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58ea8d940771f851f3e157b8fd4e8a562c6ef0e5","datavalue":{"value":{"entity-type":"item","numeric-id":4304396,"id":"Q4304396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1765237$8C814326-4991-48C7-950E-1409373126BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"458ab467d1c5397109a383d0e5c939369d06a212","datavalue":{"value":{"entity-type":"item","numeric-id":3221403,"id":"Q3221403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1765237$D3555DD9-5687-46C6-B8B8-90FE0DD86783","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18d5cfedfe66a3b5d774d6c8fbd31b828323bdab","datavalue":{"value":{"entity-type":"item","numeric-id":4527015,"id":"Q4527015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1765237$34F9FA6B-A984-42E5-AF8A-792DF4927EED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"317583958716e5966cfa9cb1274ad2f7a41dce49","datavalue":{"value":{"entity-type":"item","numeric-id":1175958,"id":"Q1175958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1765237$9346F933-583B-4E81-B37F-9FC00542FF63","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f54a5e3832f77f7ec58de86e44e572769403e95c","datavalue":{"value":"10.1016/J.DAM.2003.11.006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1765237$A1E12916-7CC3-442A-BE6E-C1D34BDBD650","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b467aed72a41c876dade534e039e3af95d4b507","datavalue":{"value":{"entity-type":"item","numeric-id":1924226,"id":"Q1924226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c43f93a7e211dfe5f046f1ec32e41c18f7668f50","datavalue":{"value":{"amount":"+0.9435017","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1765237$45E2C01E-00CA-4CDD-A5B2-AB71A22B7BAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c9116bc5d00d3feaf074f51e1cb48ba6352503e","datavalue":{"value":{"entity-type":"item","numeric-id":1058796,"id":"Q1058796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"499b13137445320939fd5c84de7063a5d6b24c85","datavalue":{"value":{"amount":"+0.94136417","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1765237$D1DA1AEF-8968-43F7-A925-52D07882F581","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5c396604a29060070edaf01f509a6daaf824612","datavalue":{"value":{"entity-type":"item","numeric-id":4222173,"id":"Q4222173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64e1ceb80b015cf229c70b82a0e06edb52e36db1","datavalue":{"value":{"amount":"+0.9309122","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1765237$4BF8C53D-0E64-401C-BF00-4DD7817F9507","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d0c46c8aef6c0679a2562099d6772d05e4fc823f","datavalue":{"value":{"entity-type":"item","numeric-id":5175786,"id":"Q5175786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5eeae3b9c2673afff83077dcc1a63aa413b4f22b","datavalue":{"value":{"amount":"+0.9193541","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1765237$F2B060E7-C892-43CC-A885-FC5B2B754B5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5289c8e196f454e0be7b5cca5ead8a28cbb9c201","datavalue":{"value":{"entity-type":"item","numeric-id":1291117,"id":"Q1291117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5675755afd59911565165b9d0c2f61203f2dd28a","datavalue":{"value":{"amount":"+0.9129735","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1765237$1F302FF0-60DD-457F-BEA1-53E0F14E8624","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05dd6ddbc34d35b6359024c5378e9c4d10f0945b","datavalue":{"value":{"entity-type":"item","numeric-id":1827869,"id":"Q1827869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d46c4e1709704613ee9eea364afdf493fd5cb046","datavalue":{"value":{"amount":"+0.91099536","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1765237$3B26C2F2-7C51-4CCD-BC06-00338B6414BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06c784d89dd1a5de78c4923e9de5d2c21d423164","datavalue":{"value":{"entity-type":"item","numeric-id":2741467,"id":"Q2741467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d46c4e1709704613ee9eea364afdf493fd5cb046","datavalue":{"value":{"amount":"+0.91099536","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1765237$DCC815A4-9B36-47AE-8378-63169FC9C84B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12fa3cfec3f05bb7e5fc125fe59912706dedf11a","datavalue":{"value":{"entity-type":"item","numeric-id":1378499,"id":"Q1378499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c51fc7efb59ef61f0865b87a1f8e770cd0d1ef5a","datavalue":{"value":{"amount":"+0.90656424","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1765237$1810AFBB-4219-4FC1-93D9-83C80792EEB2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Optimal covering designs: complexity results and new bounds","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Optimal_covering_designs:_complexity_results_and_new_bounds"}}}}}