{"entities":{"Q1356502":{"pageid":1367241,"ns":120,"title":"Item:Q1356502","lastrevid":70954524,"modified":"2026-04-13T18:28:42Z","type":"item","id":"Q1356502","labels":{"en":{"language":"en","value":"Graph domination, tabu search and the football pool problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1018581"}},"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":"Q1356502$429CA74A-3523-481F-9F69-041A916296EC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a17b5e26ec887bf80e60a4c0a692cb8882807d65","datavalue":{"value":{"text":"Graph domination, tabu search and the football pool problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1356502$FB1FB141-6B38-474A-AC35-597F70C96333","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4423d0368bf078fa7048b0531ee42089c28e0fc5","datavalue":{"value":"0884.90125","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356502$AE3C4802-1554-45FF-BF46-577E1EAF114E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7b5edd13b8eb491da2141d9bb6d6ef9d397ef7ff","datavalue":{"value":"10.1016/S0166-218X(96)00049-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356502$84C2F3C1-E008-4669-B419-E96F0A81F9D4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"977450ad0f208151966089726af0717b973bb301","datavalue":{"value":{"entity-type":"item","numeric-id":1356501,"id":"Q1356501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356502$339A6659-46A1-40D3-ADB9-7E79AD996C6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"346b5381a36e3457d87287d032ebcb64002e719a","datavalue":{"value":{"entity-type":"item","numeric-id":412174,"id":"Q412174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356502$038E8E69-45BA-4544-A441-A7E2004FC832","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":"Q1356502$382CED81-9BF2-46D1-A294-E71B075B783E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e2b9e5433934744776676f83620c488e28cd2a60","datavalue":{"value":{"time":"+1998-04-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1356502$F18828D2-B280-4DBB-B243-9758AD6228D5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3395a2cd6863e39784161d0f578415f36fc38e6f","datavalue":{"value":"http://www.elsevier.com/locate/dam","type":"string"},"datatype":"url"},"type":"statement","id":"Q1356502$1F837B82-0A73-4BF0-AE4D-AEACDF98D897","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fd236417d97e7ec35c19afb3fa03585b94c9dd0a","datavalue":{"value":"Finding the cardinality \\(\\rho_n\\) of the smallest ternary code of length \\(n\\) with covering radius 1 is known as the football pool problem. The value of \\(\\rho_n\\) is known for \\(n\\leq 5\\) and \\(n= \\frac12 (3^k-1)\\). The best upper bounds known at present were found by using simulated annealing or other heuristic algorithms combined with a theorem of \\textit{A. Blokhuis} and \\textit{C. W. H. Lam} [J. Comb. Theory, Ser. A 36, 240-244 (1984; Zbl 0533.05020)]. See also \\textit{P. J. M. van Laarhoven, E. H. L. Aarts, J. H. van Lint} and \\textit{L. T. Wille} [ibid., Ser. A 52, 304-312 (1989; Zbl 0724.90085)] and \\textit{P. R. J. \u00d6sterg\u00e5rd} [ibid., Ser. A 67, No. 2, 161-168 (1994; Zbl 0815.94023)].    The problem has been generalized to mixed covering codes as follows. Define \\(K(t,b)\\) to be the minimal cardinality of a subset \\(C\\) of \\(\\mathbb{Z}_3^t\\times \\mathbb{Z}_2^b\\) such that every point in this set differs in at most one coordinate from a point in \\(C\\). So \\(\\rho_n= K(n,0)\\).    Tabu search is an approximation algorithm for combinatorial optimisation based on neighbourhood search. The power of this algorithm is tested by applying it to finding upper bounds for \\(K(t,b)\\). Several of the results referred to above are reproductd and the computing times are compared. Some of the results were found independently by \\textit{P. R. J. \u00d6sterg\u00e5rd} [`Constructing covering codes by tabu search'; preprint]. New bounds are given in the cases \\(K(4,4)\\), \\(K(4,5)\\), \\(K(6,5)\\), \\(K(7,6)\\), \\(K(8,5)\\), and \\(K(9,3)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356502$D99D07E7-2628-4961-9B04-128DF6D99293","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356502$E0542B6B-06B9-414F-B46C-2D5F5AEDEE61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f4c7782f72175e3602c0085cb3bfabe8f23ebb24","datavalue":{"value":"94B99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356502$7B4CCD28-C80D-488E-846D-893EF269453B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356502$C11786E1-F56D-403F-88D0-3F283EB60EC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356502$C798B508-CE5A-44E1-A85A-5E0D86FE871B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"418d4d19aa7c87e33d52e580c9c108a1bc2de096","datavalue":{"value":"90C90","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356502$884E86AC-286E-48F5-8C41-2663BE2AF4B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356502$0DE16AA2-108E-4102-9563-800A0B1F25E6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b3c2086ebee4d5179c373a286258cd8bec57baeb","datavalue":{"value":"1018581","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356502$A96908A0-CEA8-43BB-8C9B-6B2CA68F57C8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"07f337499764ef632ff2f86178953184154de9d8","datavalue":{"value":"football pool problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356502$9708FDAA-9DA6-4CC0-868B-F9F9F796142E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"203dee038d8a25e289b18f304311ab2cab671b68","datavalue":{"value":"mixed covering codes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356502$FBC1630A-18F4-4F2C-B0F1-987D34CC6954","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c8e00475554cb95f00d16db197d5817dede1318d","datavalue":{"value":"tabu search","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356502$F3F01075-0114-450B-8BDC-2297509FE97E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b383b89e956203d6486afa84b4c0c897f7766b4d","datavalue":{"value":{"entity-type":"item","numeric-id":753817,"id":"Q753817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356502$ABFABB0E-6544-49B1-83EC-19A7A8DC789B","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"e7e6827c5fd59632d48d17e5c0f38766287897fd","datavalue":{"value":{"entity-type":"item","numeric-id":20565,"id":"Q20565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356502$CADD2345-934A-41D1-8DC2-C33703DE6100","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":"Q1356502$B9231EF8-A156-45F9-A60A-AB27ED5544F0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"73065e1f99acfea60791aaa874a6b317e685fafe","datavalue":{"value":{"entity-type":"item","numeric-id":4770409,"id":"Q4770409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356502$54C78817-4F1A-4F3A-9DBB-3FA5BE4A6F74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e856196e833dbf9d9d18e2890f7a1d62e4c35ae","datavalue":{"value":{"entity-type":"item","numeric-id":789394,"id":"Q789394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356502$E7F757A4-758E-466A-80DE-4009A890C979","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b23e7bc5a087cd8dcbc80276e5103647248fb256","datavalue":{"value":{"entity-type":"item","numeric-id":4000288,"id":"Q4000288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356502$B662C9DC-FE96-4BC3-BF29-51D40ED2EF3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e22917071da3c85538b7953a4760df621a8c5844","datavalue":{"value":{"entity-type":"item","numeric-id":1356502,"id":"Q1356502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356502$086435C1-9659-4F58-B1EE-44F55D7C3D69","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":"Q1356502$9F2CC73E-4E20-4C4A-B0A8-B9A9D925B9EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f035cbd5bfdfa30363685c780e4751ea77675422","datavalue":{"value":{"entity-type":"item","numeric-id":2366991,"id":"Q2366991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356502$D63B372E-F6AF-4917-BF8C-23FB1A7F651E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f5e03eda8b209d0eec7ecf5251efc8b2588b8d3","datavalue":{"value":{"entity-type":"item","numeric-id":4354785,"id":"Q4354785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356502$3A0EA6C4-D448-4048-AC0D-F4D2B636C857","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ac5f2916c5038b32893e1cb4eb6b0b4482830f6","datavalue":{"value":{"entity-type":"item","numeric-id":753795,"id":"Q753795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356502$B2E6031F-CCFC-4A03-96F6-5DBA97AC958D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35d323506ed5fa56454127e449a91ad27bfc032c","datavalue":{"value":{"entity-type":"item","numeric-id":1208049,"id":"Q1208049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356502$50E1790C-1BB4-4E06-B907-395A6B97334D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0415a57c3e3b7884f318ab74d1cd35074ca47561","datavalue":{"value":{"entity-type":"item","numeric-id":1358675,"id":"Q1358675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356502$CC63C6B3-CC08-4F10-B765-80B37E03E0F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8cd76e5408c682e6a460f9f33a9d7b1f535bf865","datavalue":{"value":{"entity-type":"item","numeric-id":4222145,"id":"Q4222145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356502$0481F907-6BB1-428E-A7A5-22C5CF454F47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8123cdb7092eecab6c96f2dbad22a6563d74a726","datavalue":{"value":{"entity-type":"item","numeric-id":1331131,"id":"Q1331131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356502$D5A7C7FC-15D8-473B-9D29-9D8A29CA9D92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7bd3bbd7236e7ef87c6f5088e1b0ce140d6950b","datavalue":{"value":{"entity-type":"item","numeric-id":3809582,"id":"Q3809582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356502$A7D8BED1-1628-4DBB-A381-A9BB7951DA64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f49d67ff8335d7a96f5487e7c349dd9482c1b728","datavalue":{"value":{"entity-type":"item","numeric-id":2277164,"id":"Q2277164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356502$4963A320-899B-4DBA-AC2E-047EEEA7A9EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48b283095d109b0356e3b27c4298c37b5d8c2ec9","datavalue":{"value":{"entity-type":"item","numeric-id":1117236,"id":"Q1117236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356502$F9D69346-0019-4910-950E-EADA8004FF39","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f475240df0c5e27b65d73c7bae5017d8af5005d","datavalue":{"value":{"entity-type":"item","numeric-id":4222145,"id":"Q4222145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ddc4d7dffa65eba6d83ea9b6889e96badbd3afb","datavalue":{"value":{"amount":"+0.8893679976463318","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":"Q1356502$6DDE295D-0841-4754-ABAB-C5BFA8B56B52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96b6e62e54f2b5ebd06168fcba83f9ebcdc811e4","datavalue":{"value":{"entity-type":"item","numeric-id":4393247,"id":"Q4393247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2487e80bc42af76dde32f8a288defd742d81d23","datavalue":{"value":{"amount":"+0.8354708552360535","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":"Q1356502$94A68121-A106-46A5-B7C3-84CB7A354484","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"81550666afb704f57c69ea3d30bed424949dcdfc","datavalue":{"value":{"entity-type":"item","numeric-id":3100150,"id":"Q3100150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d85214885c7593e63e80eaa0064b918890d0cac5","datavalue":{"value":{"amount":"+0.8204994797706604","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":"Q1356502$65F74DB4-20A5-4873-A2F5-C7F1B3CA2493","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63180705cd391a270d58aad5b5d0b76d4aa9cc22","datavalue":{"value":{"entity-type":"item","numeric-id":3831025,"id":"Q3831025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b0cdf5026601681dcb7d87ef3b37454ca44a2bb","datavalue":{"value":{"amount":"+0.8156663179397583","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":"Q1356502$49E96376-822D-4D8D-B2E3-5788056CFDFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba5964e0dda58e7c44fca4815b0cca867f3c2b7d","datavalue":{"value":{"entity-type":"item","numeric-id":753795,"id":"Q753795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"957bc6bb61c268b40670e7bf7015f0a8dc2d1ee2","datavalue":{"value":{"amount":"+0.8153918385505676","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":"Q1356502$7D98CBE1-E440-4E3F-BA6F-5D095700E29C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Graph domination, tabu search and the football pool problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Graph_domination,_tabu_search_and_the_football_pool_problem"}}}}}