{"entities":{"Q2331611":{"pageid":2342354,"ns":120,"title":"Item:Q2331611","lastrevid":71867985,"modified":"2026-04-14T01:04:16Z","type":"item","id":"Q2331611","labels":{"en":{"language":"en","value":"Efficient approximation for restricted biclique cover problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7124203"}},"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":"Q2331611$CCE60CE5-34A2-418F-8D35-49E4A8ED518B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"42e5c2289c5c6a84907368171db448902badd01e","datavalue":{"value":{"text":"Efficient approximation for restricted biclique cover problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2331611$1FD3E2AA-C0D7-48E8-B39F-07B5D4C422A2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ce6c89e8f39d00c53f13c84041db91a6a9da5cf1","datavalue":{"value":"1460.05154","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331611$D154030C-DEB6-460E-B400-D6616E649E98","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e5c9612754a27b41d5c9d4a6e3eeacfc914d45a9","datavalue":{"value":{"entity-type":"item","numeric-id":2331610,"id":"Q2331610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331611$0460ECC8-0146-43FB-BBDE-247459174BFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bb601144f50446ab918878975754b8b11688e0e2","datavalue":{"value":{"entity-type":"item","numeric-id":477097,"id":"Q477097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331611$E34836BC-EDE6-4C5B-8410-EF6314B8F887","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":"Q2331611$3093E736-8F02-4773-A0B6-B96FD44B7101","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cf3c9392a3a411e1401dab8af8f22fd364f2a018","datavalue":{"value":{"time":"+2019-10-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2331611$8ABE7F41-18CA-4124-83D8-11051104A6A6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e990a367ff688a49569bca08e17696caf7b722ce","datavalue":{"value":"Summary: Covering the edges of a bipartite graph by a minimum set of bipartite complete graphs (bicliques) is a basic graph theoretic problem, with numerous applications. In particular, it is used to characterize parsimonious models of a set of observations (each biclique corresponds to a factor or feature that relates the observations in the two sets of nodes connected by the biclique). The decision version of the minimum biclique cover problem is NP-Complete, and unless P = NP, the cover size cannot be approximated in general within less than a sub-linear factor of the number of nodes (or edges) in the graph. In this work, we consider two natural restrictions to the problem, motivated by practical applications. In the first case, we restrict the number of bicliques a node can belong to. We show that when this number is at least 5, the problem is still NP-hard. In contrast, we show that when nodes belong to no more than two bicliques, the problem has efficient approximations. The second model we consider corresponds to observing a set of independent samples from an unknown model, governed by a possibly large number of factors. The model is defined by a bipartite graph \\(G=(L,R,E)\\), where each node in \\(L\\) is assigned to an arbitrary subset of up to a constant \\(f\\) factors, while the nodes in \\(R\\) (the independent observations) are assigned to random subsets of the set of \\(k\\) factors where \\(k\\) can grow with size of the graph. We show that this practical version of the biclique cover problem is amenable to efficient approximations.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2331611$9ABF17E3-DA30-45BC-BA67-7057BBC37335","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331611$383381AC-09BB-4EDB-B4FD-C1C342C97677","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331611$EE6CF145-02E3-45BD-A97E-F530C4D6C3FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331611$5C1D15EC-F7FA-4868-9824-9CFC426A7D3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331611$AB2C17F6-7A97-4E6E-86B6-E07930874051","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b7275e0d4b526075acce84a242d8537e929bb2d","datavalue":{"value":"60C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331611$37E4FF12-D6AF-4DDA-91C8-21BFB491FF4A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fe2c954949bbd10213f286af12ccebdeb91ba606","datavalue":{"value":"7124203","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331611$F4AD1D54-98CD-4024-A993-A6C5EE19D080","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea2fe13d487cee6b1e9a41271978549a7fa2de79","datavalue":{"value":"biclique cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q2331611$C915B5ED-E167-4ED0-B54A-2B476B51F429","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2331611$E44D0E7D-66FA-40F2-9C1C-707BA67F1A9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed819d96bc7cff24691938b6313255b68e60e95e","datavalue":{"value":"probabilistic models","type":"string"},"datatype":"string"},"type":"statement","id":"Q2331611$5B353A1C-6297-4691-A3F3-5E96EFC57AEA","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":"Q2331611$4848D7DC-92D3-4941-AA3C-F303705E8D0B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8034d842297009ccb3375086829a4b67c8b3bc60","datavalue":{"value":"https://doi.org/10.3390/a11060084","type":"string"},"datatype":"url"},"type":"statement","id":"Q2331611$00B03CCB-52FB-41F0-980A-C5433B35D587","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5b4ce0a9087ef469005332107f0cffcd27a38691","datavalue":{"value":"W2808027536","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331611$625CC472-5402-4E16-9A65-7B5805EBFB6D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea36f1a7a0ca36ce40735cc1c727a40d09fee6cf","datavalue":{"value":{"entity-type":"item","numeric-id":2921408,"id":"Q2921408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331611$19625594-F124-4820-AFD6-8DFE7B448BDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c9d5d05dcc08f4f12e5993b417e201832081863","datavalue":{"value":{"entity-type":"item","numeric-id":1019181,"id":"Q1019181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331611$2134F9AF-CD1B-4202-8674-AED06DD2BF32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9769d321bd762ae9b58f1239ad513d976518a2b3","datavalue":{"value":{"entity-type":"item","numeric-id":3477970,"id":"Q3477970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331611$855A9AA5-9888-462B-8B8E-4D883C35AEEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa1e33f3350b731e2f34864bda3b1ffb9e25f467","datavalue":{"value":{"entity-type":"item","numeric-id":5428232,"id":"Q5428232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331611$B122C181-C6D6-41C4-9890-CDBC763E66F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb8ee0c7ca8b3c46e7347c6d56d26d4c083f2f2b","datavalue":{"value":{"entity-type":"item","numeric-id":4152571,"id":"Q4152571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331611$D84FEA13-A424-4E90-B9F8-B17DBE14BE0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"418337ec0556b92fd1368edf814c6a838bdd6350","datavalue":{"value":{"entity-type":"item","numeric-id":1025967,"id":"Q1025967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331611$BC5697C4-54A6-496A-8458-ED719E9EFAA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f33613607c885b77ec1d9046247a06b1542f7725","datavalue":{"value":{"entity-type":"item","numeric-id":418168,"id":"Q418168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331611$92B00A7F-C2ED-4954-BEF9-DF6E1FFC441A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fdf5b8cde129dad7b1f19100a2902cfe3c73387","datavalue":{"value":{"entity-type":"item","numeric-id":1252795,"id":"Q1252795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331611$4500659D-112A-4EFA-A777-7108B3E73154","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba3704fb85f9982adef42ba2a6c2ba858c3cecc6","datavalue":{"value":{"entity-type":"item","numeric-id":5305869,"id":"Q5305869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331611$4774F903-76F4-4B10-9DCD-7243858551D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2791d36d014da539a066ad624c98491d53591e3","datavalue":{"value":{"entity-type":"item","numeric-id":3595486,"id":"Q3595486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331611$1D84ABE3-DE0D-40F7-85A1-062A49DB3117","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45afd92774d320e3507b8930999dd9e2ad5359e2","datavalue":{"value":{"entity-type":"item","numeric-id":1910576,"id":"Q1910576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331611$966080D7-2367-4305-8439-A7B5865805A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96c3586d0c57c7858660944bedd2ac17bc892e65","datavalue":{"value":{"entity-type":"item","numeric-id":1270816,"id":"Q1270816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331611$ADBB5A02-4FA1-44E7-BAA2-7E9D9928F294","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf259006c74a21fb245a199f7433514fa529de9c","datavalue":{"value":{"entity-type":"item","numeric-id":2775896,"id":"Q2775896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331611$A2E41DAE-B2EB-4B0C-AA9B-168051B3C41E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de3a2d35befb132f1e4604223fc8f67e9a6f59ec","datavalue":{"value":{"entity-type":"item","numeric-id":3466357,"id":"Q3466357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331611$E708278E-8793-4C11-A359-ED77FBB7896F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20ecdad41b5a7ad19af25d12395ebbff6dd994fd","datavalue":{"value":{"entity-type":"item","numeric-id":4448764,"id":"Q4448764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331611$BA8F32CA-59CB-4FC1-BDF9-8B4C9FA4E7F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8841424a46c2ac3531bdba4734ffccd1a754c5ca","datavalue":{"value":{"entity-type":"item","numeric-id":1346772,"id":"Q1346772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331611$3EB47490-B3D4-44B4-B16D-0F1191619C67","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0b70f178c5f14068ffa81efc57491509a47c220a","datavalue":{"value":"10.3390/A11060084","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331611$C20B1031-9E84-40D3-BFC3-A893D7DEF128","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"952fa3ea4d4cf9d665aa2aa912b1ecc8a11bba15","datavalue":{"value":{"entity-type":"item","numeric-id":1019181,"id":"Q1019181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"10e529e7450d14106e0f6a8a21c03893e6c986cb","datavalue":{"value":{"amount":"+0.8133102655410767","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":"Q2331611$D8A5CA76-532F-4AA9-9A47-0D54CCDFDE63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"969b73319ecfebdcd0bc335b58d6a1f5497cc04f","datavalue":{"value":{"entity-type":"item","numeric-id":5458846,"id":"Q5458846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"767b3a4f2be2504dd0a7c2ff59afdb04b06ce4ac","datavalue":{"value":{"amount":"+0.8072532415390015","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":"Q2331611$55BDE03D-A58A-461B-9A35-319E56006126","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f0e38edf39fd98ae1f67de4212d190b1d3c0865","datavalue":{"value":{"entity-type":"item","numeric-id":4634394,"id":"Q4634394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f34f9e71ee9e1bff53232e8aad0001270c5858b8","datavalue":{"value":{"amount":"+0.7867394685745239","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":"Q2331611$250DA29B-2928-416A-8741-6C88F56C2F76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3bdc7b4285a69d09af89d143f4ef7b9a1650e1ab","datavalue":{"value":{"entity-type":"item","numeric-id":2921408,"id":"Q2921408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24192ad9ba411464d230903948317090874ee041","datavalue":{"value":{"amount":"+0.78388911485672","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":"Q2331611$B2FC344D-8407-41A6-B708-E9682289AE6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8605d5e755678fab520458f430310c474a1f568","datavalue":{"value":{"entity-type":"item","numeric-id":4598138,"id":"Q4598138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0c83ad2a27c1916df5ccef8210350c9799384fc","datavalue":{"value":{"amount":"+0.7733867168426514","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":"Q2331611$2B95897A-1439-4E58-9172-777F89672738","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":"Q2331611$B1EEE18C-C33A-4A2F-A877-1B1C4EB74BD1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Efficient approximation for restricted biclique cover problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Efficient_approximation_for_restricted_biclique_cover_problems"}}}}}