{"entities":{"Q289911":{"pageid":291678,"ns":120,"title":"Item:Q289911","lastrevid":60682752,"modified":"2026-04-10T18:29:29Z","type":"item","id":"Q289911","labels":{"en":{"language":"en","value":"Configurations and minority in the string consensus problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6587982"}},"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":"Q289911$5BD69096-0830-4C02-B2DA-86174F399D27","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c162158c7f63926361a134f7daa17dbe19b8498d","datavalue":{"value":{"text":"Configurations and minority in the string consensus problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q289911$E08A7E23-288C-49A1-B810-460D59311AB6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b0a77c6f1a830554d65b7177b13d67b47caa0a4a","datavalue":{"value":"1344.68305","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q289911$20EC6AAF-9F87-43E5-B877-C172919A5BA6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1d4816a3d2e9952065dbb8659dda0ea05337b6f4","datavalue":{"value":{"entity-type":"item","numeric-id":287044,"id":"Q287044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q289911$6480F10B-A670-4281-99D7-BA08FEE96C28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c89c7c192d0562ebfd1856de3a284cdcf34a6bb8","datavalue":{"value":{"entity-type":"item","numeric-id":289910,"id":"Q289910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q289911$EB723173-2984-452C-848F-18323D14287A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a696ac940d028b864dab1bfd979b9c0923bca974","datavalue":{"value":{"entity-type":"item","numeric-id":251302,"id":"Q251302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q289911$6299A39F-C4C1-4E09-A9EB-A01CC87BEAC2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q289911$D4EB4349-D061-4482-BEEB-D831487ED32D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a2a49183d98fdb45af485077728faee3522a457e","datavalue":{"value":{"time":"+2016-05-31T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q289911$82B2D5BE-ECE5-4D73-BACF-5705383CC4CB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"efc0eef3e16ad09377e67ea96dcc4afcb31b2431","datavalue":{"value":"For the Closest String Problem we are given \\(k\\) strings of length \\(\\ell\\) and asked to find a so-called consensus string minimizing the maximum Hamming distance between any of the input strings and that consensus string. The authors present two algorithms that solve this problem exactly, which they name the Configuration Algorithm and the Minority Algorithm. The former is simple, incremental (i.e., it outputs the \\(i\\)th letter of the consensus string after reading the \\(i\\)th letter of each input string) and runs in \\(O (k^2 \\ell^k)\\) time. The latter is more complicated but allows the authors to find a consensus string for five input strings in only \\(O (\\ell^2)\\) time. The authors note that \\textit{J. Gramm} et al. [Algorithmica 37, No. 1, 25--42 (2003; Zbl 1058.68119)] already gave an algorithm that theoretically uses \\(O (\\ell)\\) time for any constant \\(k\\), but that it is impractical for more than four input strings.","type":"string"},"datatype":"string"},"type":"statement","id":"Q289911$3EFFCBD3-A88D-4651-8F01-DC146E4825CE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"190982f8ef5a79efe62543507a2f94a300470907","datavalue":{"value":{"entity-type":"item","numeric-id":390357,"id":"Q390357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q289911$D3DCB801-895C-4BE2-B836-38EFB3ED5996","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"824c9242ee6f86c15bf4eecb8cafeab39e222c2d","datavalue":{"value":"68W32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q289911$5C858E5C-2357-456C-A977-87478CDCFF46","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9eb27336870bf22385dc2158e753ed2c63533c9f","datavalue":{"value":"6587982","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q289911$F9ADAF90-B85E-4F44-B085-69717BC08D22","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b03b84a8bebabeb721db6c60531604e9df33a80b","datavalue":{"value":"closest string problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q289911$FB40461F-65B5-4420-8B3C-2CBA5E3CEDEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7e507470f9b21b1d2b7c7e2c1808bd7d3af3f83","datavalue":{"value":"Hamming distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q289911$2212EF63-4624-4B70-A5E6-D0FC8D31FAF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"02b35a15c7e77dbebfd824046bbdeda35d918f4d","datavalue":{"value":"consensus string","type":"string"},"datatype":"string"},"type":"statement","id":"Q289911$AFDE3BEE-78C9-475C-A793-DF5DB8B97131","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e726393fb20f001aaaec0d8f6722ad60fbc34bc","datavalue":{"value":"configuration algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q289911$A799D4EB-5480-418A-ADCE-3BFA7D8DD201","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5f65d21253be034988d4ccf412fff9d02119988e","datavalue":{"value":"minority algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q289911$C067862C-68AC-45AC-9C98-8F72B00C4CB0","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":"Q289911$E7FAA717-7A63-4711-A0B3-AB45DD687AC0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c814dbdb8aa782d094dd166d876d1e17b1580b09","datavalue":{"value":"https://doi.org/10.1007/s00453-015-9996-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q289911$C028FFF9-5A4E-479D-B029-5526972119DF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5503722652ed90b867324795e21e1b59ce60d99b","datavalue":{"value":"W2018731567","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q289911$DDBDF317-270A-4462-951F-0DE1FD529B4A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"af36cb1f3080a1e6703568d1b18f4da145aed2a0","datavalue":{"value":{"entity-type":"item","numeric-id":3586187,"id":"Q3586187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q289911$7ABC3329-BD05-4D50-A6FD-82EDBB7C2C07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1725e87e22968377e8bee3b93bd45dab2cf7b0af","datavalue":{"value":{"entity-type":"item","numeric-id":289911,"id":"Q289911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q289911$17E95D4A-0C43-4FB6-85E3-353C85481AE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4ae85b74cd18c4f4082ce00bf4740968f96a532","datavalue":{"value":{"entity-type":"item","numeric-id":1424248,"id":"Q1424248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q289911$B5E49223-0C91-43B2-8229-84D0AD68F92B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df92bd73445dbe3246228a0018de5d5dd067d1a1","datavalue":{"value":{"entity-type":"item","numeric-id":1427861,"id":"Q1427861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q289911$B61B9D8F-98D6-4357-A5CD-B4A087D2BF21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02901919df95c5cfee893a7b08627856779e1e47","datavalue":{"value":{"entity-type":"item","numeric-id":3196639,"id":"Q3196639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q289911$917185C5-4358-4AB7-986F-C16FED4FDC97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88df7aa4b23279e1501e5a5ab818e9475ac8149b","datavalue":{"value":{"entity-type":"item","numeric-id":5233693,"id":"Q5233693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q289911$89443237-68F8-4E1C-AB60-7EB7874AC211","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a32f9eb182c7461392b0c1bec9e662087c05f8f","datavalue":{"value":{"entity-type":"item","numeric-id":675858,"id":"Q675858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q289911$F2A628F8-8F73-484A-9DFB-AC32ADCB54FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75ba39de95401ef46d7fe45724c5b7288bb0492a","datavalue":{"value":{"entity-type":"item","numeric-id":4474112,"id":"Q4474112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q289911$442405A1-3844-46B6-9B81-00F010D156E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"483baa18f2fbe1fd85cdbed020324506d0be99c5","datavalue":{"value":{"entity-type":"item","numeric-id":2890443,"id":"Q2890443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q289911$39EE076B-3F6E-4C7A-8B5E-0D289640814C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7b369429581047e1dabd46e6eafe270ef5ac985","datavalue":{"value":{"entity-type":"item","numeric-id":3037135,"id":"Q3037135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q289911$6C828E02-D90E-4127-B0AE-E362088B91C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da6debf5ac33cbc2913abdf90b0edc322a7ce022","datavalue":{"value":{"entity-type":"item","numeric-id":5096932,"id":"Q5096932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q289911$2B41A9DB-FC3E-4CEB-AAAD-985A4CE89998","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4c91dd568a033a578228f802ed7df6c47d8eae6e","datavalue":{"value":"10.1007/S00453-015-9996-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q289911$BDBADC1B-8412-410B-B64C-88E84D685AE8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a8698e41d17236d0dbe10d348ebb2b86e0fce80","datavalue":{"value":{"entity-type":"item","numeric-id":4913724,"id":"Q4913724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85fb18ec0b335940849c949f2567fc166db366e3","datavalue":{"value":{"amount":"+0.9923593401908876","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":"Q289911$10240E0E-5D84-4621-9DF8-CC911E63310E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf619afc339a3505122778247fc879b8f1b2d19c","datavalue":{"value":{"entity-type":"item","numeric-id":4474112,"id":"Q4474112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1fe3eedda7acadb2430b97c19199a03f47837ec","datavalue":{"value":{"amount":"+0.8593050241470337","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":"Q289911$A5D2CF8C-90EE-4BAF-BF4C-3171EAEA01CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c48e23386dfb5221a5b6b8243258a527e6037c8","datavalue":{"value":{"entity-type":"item","numeric-id":1424248,"id":"Q1424248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bce47ef2d24b7ea33f626ca0511ea3843a972141","datavalue":{"value":{"amount":"+0.8481394648551941","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":"Q289911$5184F141-1A4F-4CB5-BA24-3B14B67BC179","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5cbbab9587fc4a2faf7910940d14a22e850f3c9","datavalue":{"value":{"entity-type":"item","numeric-id":3395036,"id":"Q3395036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91f96c6381bf85c2b9a8fd4e535bd0cb1270939e","datavalue":{"value":{"amount":"+0.8253645300865173","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":"Q289911$258913F3-8694-4AC5-92A0-0AE882412E54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"09171ed3dbbd94dba8637a1343d372b59ff60131","datavalue":{"value":{"entity-type":"item","numeric-id":3196639,"id":"Q3196639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1e09b024bfb43945ce5df0bae2b23e51ee54b8b","datavalue":{"value":{"amount":"+0.8243376612663269","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":"Q289911$8AA4700D-0D89-4067-A78C-1B71276EB071","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Configurations and minority in the string consensus problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Configurations_and_minority_in_the_string_consensus_problem"}}}}}