{"entities":{"Q1736769":{"pageid":1747510,"ns":120,"title":"Item:Q1736769","lastrevid":73233504,"modified":"2026-04-14T15:05:22Z","type":"item","id":"Q1736769","labels":{"en":{"language":"en","value":"Co-clustering under the maximum norm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042326"}},"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":"Q1736769$BA021126-4795-4B5C-8F73-0C7FF73E648E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0be8e47b9befb78b6d6ea0d47fa20a3f9476e58d","datavalue":{"value":{"text":"Co-clustering under the maximum norm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736769$D7AB4F31-8745-460D-9E8D-D8FE753135DB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a934be7cafaadf4a4456a1443a212384b3a7d53c","datavalue":{"value":"1432.68172","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736769$31F51635-E068-49F1-A1FE-2895E2786E64","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5cd90d1379d12c9a0d4ff615a1f80bc47193227c","datavalue":{"value":{"entity-type":"item","numeric-id":324802,"id":"Q324802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736769$8E9ADE7D-A5C4-47FC-89FC-D155C8330B3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0a606ba0c6cbc27f4e2e82208a53bd54d91a6d03","datavalue":{"value":{"entity-type":"item","numeric-id":295646,"id":"Q295646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736769$1DFACBC4-0949-4EC1-AAB6-F90D4DD757F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b76370dff2699b8e5203df14aa243efdde2b064c","datavalue":{"value":{"entity-type":"item","numeric-id":249101,"id":"Q249101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736769$2FA07141-DDA7-4931-92DD-7F7881262584","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5ae9ae3d803b6f9d7df2d14c483ee95b047535f8","datavalue":{"value":{"entity-type":"item","numeric-id":175575,"id":"Q175575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736769$BDECF4CB-F975-45ED-8F9E-EE0E1D2AF18C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736769$5E8DE825-6A3C-47A9-BA53-654AFB7B97DC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d660e31d569d3203bec6d5e897b7f6ed7f6a3a72","datavalue":{"value":{"time":"+2019-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1736769$DEF0C034-2C4F-4781-B0A5-5374E336538E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"69c9aa5145ff12fbf7360e813ff03c0d2e95c5f2","datavalue":{"value":"Summary: Co-clustering, that is partitioning a numerical matrix into ``homogeneous'' submatrices, has many applications ranging from bioinformatics to election analysis. Many interesting variants of co-clustering are NP-hard. We focus on the basic variant of co-clustering where the homogeneity of a submatrix is defined in terms of minimizing the maximum distance between two entries. In this context, we spot several NP-hard, as well as a number of relevant polynomial-time solvable special cases, thus charting the border of tractability for this challenging data clustering problem. For instance, we provide polynomial-time solvability when having to partition the rows and columns into two subsets each (meaning that one obtains four submatrices). When partitioning rows and columns into three subsets each, however, we encounter NP-hardness, even for input matrices containing only values from \\(\\{0,1,2\\}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736769$5A38A3E6-C97B-4849-B9E6-11ED3A320707","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736769$0DE0A932-9B17-428C-B80D-DD1B9565688A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3a56ed6d195ea3539360546b34a91d2ad94c0346","datavalue":{"value":"15A23","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736769$1027D1E5-0115-43CD-9CF6-B620F296CE68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"48a59f52dcfcc38cd6697e0ef07319031311895b","datavalue":{"value":"62H30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736769$0539BB12-6F83-4522-BC14-9B856B6B47E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736769$B0F31EC2-9F78-4626-8B79-5C88753F6F41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ca84c0a1de3e8c9074706ad5adbc0b1d28c30279","datavalue":{"value":"68Q27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736769$7D8E16ED-8779-4611-A543-4ED658FDEBDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cfe779e91fe9c53ee133568259955801965765ae","datavalue":{"value":"68T05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736769$5C2E2974-312F-4362-98E9-036C78E94D4F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"246a9349c5e85a51abb1f40309d7c362895015b5","datavalue":{"value":"7042326","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736769$7C760BFE-50FE-47F9-A7E2-E0365A792D58","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdde73c0596b9b788a38f3b70cbe7cf9ecef061b","datavalue":{"value":"bi-clustering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736769$B3217FA3-FA75-47C4-9EB5-A2BCD47D3ABD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"21a4b086814cfc3c22657bd8171e2010266f0677","datavalue":{"value":"matrix partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736769$7A09C14C-7920-437E-8729-FD3405ED61DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d5e4886aa4290eca104cd0d1da319d8b4d34c4","datavalue":{"value":"NP-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736769$AD99356C-D2FA-49D0-8744-6A583EB58667","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f5f9a2adc04516f7806472d1c6b5b07524a09c31","datavalue":{"value":"SAT-solving","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736769$D3F743E8-FAB7-4877-83B4-CAB11730EA42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1520de8379415749656b1e95045c660d5b7f1330","datavalue":{"value":"fixed-parameter tractability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736769$64356F3C-9EF9-4BEF-91FD-FCAF94C41598","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"60c977c73f66c80db6a0782a3e55d401ee00ddc1","datavalue":{"value":{"entity-type":"item","numeric-id":19150,"id":"Q19150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736769$6B894EB9-D4C1-4CE4-A7FF-C56BF8DCC5C9","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":"Q1736769$7094E107-6E12-48CD-8373-0B3E8C2A212D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c9552a99b0d354bc6b0eb402cc6707b8068e207d","datavalue":{"value":"https://doi.org/10.3390/a9010017","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736769$AF080783-77C7-49D2-8433-628F8BD8FCCD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"50abef49790f79d79a7a7d0dea8cbe322ce577a3","datavalue":{"value":"W2138629073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736769$0A258396-BC82-414D-BC5B-06DC75A0B3DC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb9e5f4ccbcc4fd1bd1c34d7e2089b213e31f6ef","datavalue":{"value":{"entity-type":"item","numeric-id":3191565,"id":"Q3191565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736769$9D5B05F8-D3E2-4C1C-899A-900CE180E64E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88b80fd84cc3c1897c1062a722fdc60b47c8bea6","datavalue":{"value":{"entity-type":"item","numeric-id":3174147,"id":"Q3174147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736769$192FBBF3-0D11-4A77-A1C2-E2709822448E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0e24316a71073ca2d4b3db3a767c70da3a6e1e7","datavalue":{"value":{"entity-type":"item","numeric-id":5449858,"id":"Q5449858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736769$37DB3BB2-188E-483C-BB42-D4A0AE459DDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a08f555dd017a5ee29da12451d2a6f0bc9b3c84","datavalue":{"value":{"entity-type":"item","numeric-id":3648764,"id":"Q3648764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736769$9A98F651-1AFD-49B8-8E38-50B3B99F58A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08cc9cdd9999a46859ae4f667ab34baac016718b","datavalue":{"value":{"entity-type":"item","numeric-id":5502162,"id":"Q5502162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736769$B81F1BF0-DCD7-42D5-B33B-363A3CE22725","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05ccbb66f253e8aabe9f774ba9414f12634b864d","datavalue":{"value":{"entity-type":"item","numeric-id":383833,"id":"Q383833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736769$EE0B35BB-794D-4704-99E4-012BB2AC69AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e1357b15aa0895d858d392a7ff419092326aafa","datavalue":{"value":{"entity-type":"item","numeric-id":5710169,"id":"Q5710169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736769$5A3AE066-128B-46F7-9742-199DB76A12DC","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":"Q1736769$B8312EBE-8BB7-4949-A125-51480944A4B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"307fb49f6fe2fb59c207608c4367a76916d437d2","datavalue":{"value":{"entity-type":"item","numeric-id":1157170,"id":"Q1157170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736769$566A91EA-13A2-4C3F-84BA-0BF57ED81DD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9370899dedc1d653d16f1f5aaa8b6c6be96f529c","datavalue":{"value":{"entity-type":"item","numeric-id":3604000,"id":"Q3604000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736769$037EFF2E-D657-44D4-AAFB-BFE5DCCC3FA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cf035d2fecb7e445991dd16e141f37bab3768a8","datavalue":{"value":{"entity-type":"item","numeric-id":1254112,"id":"Q1254112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736769$FE8D7D31-7362-4E8B-A76F-8541A3198B63","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e9aaed707ae0ff83feb7a4aaa78e4e6c40006cc8","datavalue":{"value":"10.3390/A9010017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736769$F86D8027-AAFF-4486-8345-B83617CCAEE3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a975dc58e0a5560f0f0e6990c8ae0afee00a3bd","datavalue":{"value":{"entity-type":"item","numeric-id":2942637,"id":"Q2942637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"874e3873cb2e83790715f1a1351289bd81d26bd9","datavalue":{"value":{"amount":"+0.9960135817527772","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":"Q1736769$EF9CB288-C805-495A-91BA-4D3DEBBDE191","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4dfe2d4b207ba2d9bc3378611778f27ebabab877","datavalue":{"value":{"entity-type":"item","numeric-id":3191565,"id":"Q3191565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f02ddfd1cfde6d32fa8eed8b8c5390ef7de766b","datavalue":{"value":{"amount":"+0.8183815479278564","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":"Q1736769$3C43433F-5990-485A-85B8-314B5F3EA3E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ad3f1d2b039d946ca0eb9b06527503130a17c8b","datavalue":{"value":{"entity-type":"item","numeric-id":1719430,"id":"Q1719430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eda328a94861cfcc37c18455ec3775bcbf5e3240","datavalue":{"value":{"amount":"+0.762154221534729","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":"Q1736769$2B61E4ED-9263-45C0-ACBF-B42C2356EBBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5117a3ee3d078603e3e0d8992b49996664850d0a","datavalue":{"value":{"entity-type":"item","numeric-id":2026156,"id":"Q2026156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec6e6c8a7c4e1a5a0f821c520c8e1885f087c85d","datavalue":{"value":{"amount":"+0.758331835269928","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":"Q1736769$48C823D5-3678-4E42-86AF-A4607065EACC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4c104285bb5ef79e6c8397fd8293dbdc4566462","datavalue":{"value":{"entity-type":"item","numeric-id":4474131,"id":"Q4474131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30ba5b316ebe898cd397124f560512b579f77e1f","datavalue":{"value":{"amount":"+0.7496652007102966","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":"Q1736769$528BCCBC-EE5B-4F1F-B8B6-5E688C789402","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736769$9E1CFD37-E9B3-4365-B63B-3402158487E6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Co-clustering under the maximum norm","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Co-clustering_under_the_maximum_norm"}}}}}