{"entities":{"Q876471":{"pageid":878319,"ns":120,"title":"Item:Q876471","lastrevid":65021463,"modified":"2026-04-11T23:47:24Z","type":"item","id":"Q876471","labels":{"en":{"language":"en","value":"Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5144481"}},"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":"Q876471$B0F99607-90E9-4F9C-B87B-D4759811E51E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"eb272ac09e99a259f8082079f567de2e94a4221e","datavalue":{"value":{"text":"Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q876471$D237901D-CA88-4187-9C6C-ACC8563D2255","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d406e224e81608cc4dacb04d06cceed17a2cd88c","datavalue":{"value":"1163.68045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876471$76BC7979-1B48-44A9-9457-2A073A3372D4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"544d0b7ba4444928caddd3ee5ebd1b425c121444","datavalue":{"value":{"entity-type":"item","numeric-id":397069,"id":"Q397069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876471$FCDB175F-CF41-4692-AA8E-A7635E73125E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5692f334a12613f9a146ec30b48901e01791357c","datavalue":{"value":{"entity-type":"item","numeric-id":1709596,"id":"Q1709596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876471$51A927AE-F33E-4992-B2C1-897D6588ADD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0cb5b7427c1f32f99a1cfc4916c12f880bea90b3","datavalue":{"value":{"entity-type":"item","numeric-id":6481980,"id":"Q6481980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876471$F7A00CFA-C597-485D-AD4E-AE3A90CECBEC","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":"Q876471$5FB95EC2-F4AD-4737-B4A0-141DE28CA6A5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6f339c49c589764265da0f7de34a17b3e7a78e06","datavalue":{"value":{"time":"+2007-04-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q876471$C4A68208-1F42-4991-810B-0F13FA628D27","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"43d3b8ad160da80e40d23b5a8e9a238418ea9623","datavalue":{"value":"In this paper we investigate the computational complexity of a combinatorial problem that arises in the reverse engineering of protein and gene networks. Our contributions are as follows:  -- We abstract a combinatorial version of the problem and observe that this is ``equivalent'' to the set multicover problem when the ``coverage'' factor \\(k\\) is a function of the number of elements \\(n\\) of the universe. An important special case for our application is the case in which \\(k=n-1\\).  -- We observe that the standard greedy algorithm produces an approximation ratio of \\(\\Omega(\\log n)\\) even if \\(k\\) is ``large'' i.e \\(k=n-c\\) for some constant \\(c>0\\).  -- Let \\(1<a<n\\) denote the maximum number of elements in any given set in our set multicover problem. Then, we show that a non-trivial analysis of a simple randomized polynomial-time approximation algorithm for this problem yields an expected approximation ratio \\(\\mathbf E[r(a,k)]\\) that is an increasing function of \\(a/k\\). The behavior of \\(\\mathbf E[r(a,k)]\\) is roughly as follows: it is about \\(\\ln(a/k)\\) when \\(a/k\\) is at least about \\(\\mathbf e^2\\approx 7.39\\), and for smaller values of \\(a/k\\) it decreases towards 1 as a linear function of \\(\\sqrt{a/k}\\) with \\(\\lim_{a/k\\to 0}\\mathbf E[r(a,k)]=1\\). Our randomized algorithm is a cascade of a deterministic and a randomized rounding step parameterized by a quantity \\(\\beta\\) followed by a greedy solution for the remaining problem. We also comment about the impossibility of a significantly faster convergence of \\(\\mathbf E[r(a,k)]\\) towards 1 for any polynomial-time approximation algorithm.","type":"string"},"datatype":"string"},"type":"statement","id":"Q876471$B00684FD-3F22-4E08-853A-CE81DA670F0D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e01671c873d801b913451010c0981a684c101d40","datavalue":{"value":"68W20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876471$0E6ACBF1-9BA3-4BFF-96BC-6AFF2829F963","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876471$8A9E8CA1-5674-4490-A46C-F9E5FC69D349","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1cc6a2d1a81aec0cb5abdfe44055f934ac25329b","datavalue":{"value":"92C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876471$C573F299-4FD8-408D-BA87-B2C00FC98012","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8acfb5681686a479769f1498162f25169e468cda","datavalue":{"value":"92D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876471$DF3DC906-33C2-4357-B5EE-EFA7B60C6CB7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1d424bb686bc3b19c5abb39f1780a221832ff04a","datavalue":{"value":"5144481","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876471$15542F6A-00F1-49F3-A6EF-F843AE7891DE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"093ae6f8d8be4447d081d028ffeba3f7745b00eb","datavalue":{"value":"set multicover","type":"string"},"datatype":"string"},"type":"statement","id":"Q876471$CC6A5061-A25E-4E65-BE57-D7578D41E582","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a01519ccd061de77e4f96d99f701aae2e4e9cc2c","datavalue":{"value":"randomized approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q876471$7F09DFE8-5B97-4900-B801-162144E58073","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fea11f6858c1ce6f93aff543970cef9398e1f999","datavalue":{"value":"reverse engineering","type":"string"},"datatype":"string"},"type":"statement","id":"Q876471$766D3359-11F6-4138-9331-D41BD7C56CBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"af21a6ab343bd0fd296429b5bd11a202c10752fc","datavalue":{"value":"biological networks","type":"string"},"datatype":"string"},"type":"statement","id":"Q876471$1519AD29-8566-4BE9-B804-5784FB56A1FE","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":"Q876471$1FE3897B-2EA6-40A3-9EE7-E5BF68BC9D85","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cb3c6860b275f59008e56e6c127abc2898688476","datavalue":{"value":"https://doi.org/10.1016/j.dam.2004.11.009","type":"string"},"datatype":"url"},"type":"statement","id":"Q876471$9030C05C-A438-4FC6-B04D-A23444A96F69","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bb4767eb07f57107259801bf494cc501b66001be","datavalue":{"value":"W2163141979","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876471$669140F9-464B-4196-869D-8E0E35F8B8F2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4799e5a32c687eea79d573479ff8c58240f3cb62","datavalue":{"value":{"entity-type":"item","numeric-id":4004078,"id":"Q4004078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876471$926A7AEC-34F6-4156-BF9E-48823B878E6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09927ff534153e5dc51685893e8139da55825cce","datavalue":{"value":{"entity-type":"item","numeric-id":776529,"id":"Q776529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876471$3BB8E2B4-FE07-43C5-957C-C480B3A881DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77d6452e54e5e6983bfa6dba10e55824db2fd929","datavalue":{"value":{"entity-type":"item","numeric-id":5814290,"id":"Q5814290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876471$C7181520-BA9B-4DCB-95BB-6DA2BB3C3B64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c760a5f7f2f9c7eb535667304d6e49346fd22e8","datavalue":{"value":{"entity-type":"item","numeric-id":5531563,"id":"Q5531563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876471$CD75399C-4173-4370-BC45-23B28A1D912A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"783f5b77f65178466163307ca17329fb72140e4a","datavalue":{"value":{"entity-type":"item","numeric-id":3158517,"id":"Q3158517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876471$ADC03C3A-29F5-4E09-AA44-5A519DABADDF","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":"Q876471$D78859C2-018E-42CB-9F90-31BD1A0B3951","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":"Q876471$D13B1489-5850-4E58-BD9A-ACD98C20CFF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0b86da6901907b4b60c4d755cbdefb3d87af7f5","datavalue":{"value":{"entity-type":"item","numeric-id":761967,"id":"Q761967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876471$8302B8EF-FD5D-4B2E-AA33-03B90A58F562","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d05652188e444fc35e748b68b983451566933e27","datavalue":{"value":{"entity-type":"item","numeric-id":4856179,"id":"Q4856179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876471$C29B6B90-C7B4-4828-AB4E-617002AFAF0B","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":"Q876471$27F903C6-A7A8-4030-91D7-EAB1F87F1EE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac76c3fccb1172c29e50bbdfd956698001a40e1e","datavalue":{"value":{"entity-type":"item","numeric-id":4250971,"id":"Q4250971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876471$4DE981B3-F01E-418C-8D7E-B89994635FC2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c8096fc38aa14ef3e519c0b9475170a8fe6882c7","datavalue":{"value":"10.1016/J.DAM.2004.11.009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876471$4DA3C4F3-076F-4725-A293-2D84FCA58ADC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a3682274e55c1dacd5e933cebe59fb4101ed568","datavalue":{"value":{"entity-type":"item","numeric-id":5313045,"id":"Q5313045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5631658f982e69d4666606bc668157d8d900719","datavalue":{"value":{"amount":"+0.9999995","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":"Q876471$348A6621-F47B-42A0-A978-371A49E57EA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e112a00d94f7d6c061abe1fa8fdb7fc36bc45386","datavalue":{"value":{"entity-type":"item","numeric-id":262245,"id":"Q262245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a83d601813d15b8a479cadde0f6bc11f14d2d33","datavalue":{"value":{"amount":"+0.8713559","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":"Q876471$BDAA3CFF-3FE2-4A6F-8CFA-A65AF4C91E0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4083bac33ad347949703877f8ff7a9e813398ec","datavalue":{"value":{"entity-type":"item","numeric-id":2867107,"id":"Q2867107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b6adb0b5c3c518fd0be6b834a4532184c33c102","datavalue":{"value":{"amount":"+0.8661747","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":"Q876471$7E741B58-CA89-43A7-98DE-1AC80DD4988B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e94960fc24046bd98f181b59ae2128beda6f161c","datavalue":{"value":{"entity-type":"item","numeric-id":2870051,"id":"Q2870051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c39cf3010716766a09fbbe47396daf8cba375a6","datavalue":{"value":{"amount":"+0.85572","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":"Q876471$19E59D14-498C-4512-84A9-3321B879A043","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1f31092575ffa7f8d7cb6b6d6d1fd37425ca119","datavalue":{"value":{"entity-type":"item","numeric-id":3638443,"id":"Q3638443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df76562bf25ef337e29dfb5c927d9c42ee34f7aa","datavalue":{"value":{"amount":"+0.85367835","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":"Q876471$44503C35-777D-4B26-84C5-8C33BDB3260C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe85394864c5b0d7680cd14b7f70569fb0199588","datavalue":{"value":{"entity-type":"item","numeric-id":2485280,"id":"Q2485280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e0ee0910f437e5ece5d324f6372839d0f12ad91","datavalue":{"value":{"amount":"+0.84635067","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":"Q876471$EA98FF15-AFA2-4A65-898A-DA71C4E66F52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64699be6f408f52b52748e27f018a8dab50b3edb","datavalue":{"value":{"entity-type":"item","numeric-id":5315401,"id":"Q5315401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e0ee0910f437e5ece5d324f6372839d0f12ad91","datavalue":{"value":{"amount":"+0.84635067","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":"Q876471$9C78C099-D940-4D70-A158-E2D11060E9FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c131db67909a1d2085cd3fdf78c950033ad60b37","datavalue":{"value":{"entity-type":"item","numeric-id":3652189,"id":"Q3652189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c969a3661ff0e54a3c05bbf45f60033ac75c04c5","datavalue":{"value":{"amount":"+0.8447935","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":"Q876471$719B8CE3-EC48-4831-9BF9-C02CDCC28BD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ccab9536a2d985d6e828cf0707e3ddd40fd42804","datavalue":{"value":{"entity-type":"item","numeric-id":300233,"id":"Q300233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a14b6b194dd62ee6a4961a6f634ae384e9346a83","datavalue":{"value":{"amount":"+0.8417952","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":"Q876471$D376EDDF-00F1-43CD-A1D3-2C178B632168","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Randomized_approximation_algorithms_for_set_multicover_problems_with_applications_to_reverse_engineering_of_protein_and_gene_networks"}}}}}