{"entities":{"Q6049083":{"pageid":13183239,"ns":120,"title":"Item:Q6049083","lastrevid":41236938,"modified":"2025-04-23T01:43:07Z","type":"item","id":"Q6049083","labels":{"en":{"language":"en","value":"A bicriteria approximation algorithm for minimum submodular cost partial multi-cover problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7750448"}},"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":"Q6049083$DFBEBE08-148D-465D-B499-687258140C32","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5ca5a7d91dfc5e62eb99c0709059303822ce820b","datavalue":{"value":{"text":"A bicriteria approximation algorithm for minimum submodular cost partial multi-cover problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6049083$29FA9EAD-8222-449C-BF6F-6137901C59A7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a8f2d9c65cda48d3557342afd6e7b46959464f23","datavalue":{"value":"1525.91143","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6049083$915E0D91-F161-4C4D-BB91-B323096E0092","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"34aea6dd80bb0dd2ca3f18c3c1c70a987c629183","datavalue":{"value":"10.1007/978-3-030-04618-7_6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6049083$B2276A05-BA3F-41EB-9761-350FD57F1AEB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0e9193a4cc51f1724cadd2009462e70d23dd055d","datavalue":{"value":{"entity-type":"item","numeric-id":247822,"id":"Q247822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6049083$31C1D6A9-931B-48A1-9991-4FE99E68A760","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"749db56ed30793be45710afd38c1d1914e89240e","datavalue":{"value":{"entity-type":"item","numeric-id":247824,"id":"Q247824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6049083$56D96633-FE34-44CA-9D16-D2789125EFDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2d176dcf8014bfec2c4899579ee7ce9e18294338","datavalue":{"value":{"entity-type":"item","numeric-id":166203,"id":"Q166203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6049083$B36A2B0A-323F-4617-BE2E-CE3F8E969517","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"2cfd8de7e3f063c1909df2c6598df99004932242","datavalue":{"value":{"entity-type":"item","numeric-id":2830052,"id":"Q2830052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6049083$9DB59A53-4DEF-41EA-8635-94FC2EE4DF66","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d7cec1d6c26b437b8346d60916c61f4d1667636a","datavalue":{"value":{"time":"+2023-10-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6049083$F084093C-F6F7-437F-8F0C-438117783B19","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6b2b752158acc503ef606112076f6c341d266895","datavalue":{"value":"This paper studies a bicriteria approximation algorithm for minimum submodular cost partial multi-cover problem. The problem is studied with a profit on each element and it aims to find a minimum cost sub-collection of sets such that the profit of fully covered elements is at least \\(q\\)-percentage of total profit. A randomized \\((O(b/q\\varepsilon),1-\\varepsilon)\\)-bicriteria algorithm is presented. The algorithm produces a solution covering at least \\((1-\\varepsilon)q\\)-percentage of the total covering requirement, and achieves performance ratio \\(O(b/q\\varepsilon)\\) with a high probability, where \\(b=\\max_e\\binom{f_e}{r_e}\\) and \\(f_e\\) is the number of sets containing element \\(e\\) and \\(r_e\\) is its covering requirement.  For the entire collection see [Zbl 1400.68037].","type":"string"},"datatype":"string"},"type":"statement","id":"Q6049083$E1E85239-E5CD-4341-9B8B-6138D09BF902","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cf7697837a2bc77bf648f6498699f73255ce7dba","datavalue":{"value":{"entity-type":"item","numeric-id":278372,"id":"Q278372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6049083$369634C3-E82C-468B-A024-6BDA6338F5FC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"510d3c71187dca01ea55ca1a3a98ebbed84a7e74","datavalue":{"value":"91D30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6049083$83660891-749E-446F-9206-5B702EE1F4C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6049083$142B2A96-EF97-4252-BECA-A23FF2A12B12","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"46ab102f102702e7cba32aa1fe15f4c67631c58a","datavalue":{"value":"7750448","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6049083$7180F9A5-2A94-44CF-9D09-E18E75520434","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"66e1a1213682950f63f65fd446a2b75328c1ae4a","datavalue":{"value":"partial cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q6049083$927003AC-F7F9-4F3D-B52C-C747EAD9BB40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c21a12f9a3867eea75ddd5ccff5b8a342c09b04","datavalue":{"value":"multi-cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q6049083$BD4EA200-5F19-43B1-9DB8-50FF90766D73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf9fffdb87740d9e7d9478787153eaf198b92ea8","datavalue":{"value":"submodular cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q6049083$E1DDFBD5-5FD4-4583-A7C6-DCE07C726088","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8db7e89babadb7e0f97a4d87937cf02f28d1cf58","datavalue":{"value":"bicriteria algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q6049083$DB975A17-6E38-42F8-B722-419A924FDC29","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":"Q6049083$0F519A2D-F18B-48B8-A72B-4EA2222DAA77","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc7a01b96f9a15a0f7df23473c0a4cb576f17793","datavalue":{"value":{"entity-type":"item","numeric-id":2282997,"id":"Q2282997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7cebda04720a196a183e75e30936cb07e0ee3f1","datavalue":{"value":{"amount":"+0.98429084","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":"Q6049083$C90D2DEF-3157-4754-AB76-E4D515AC4967","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43940111cee352a614f8f21196a1100d413d48b2","datavalue":{"value":{"entity-type":"item","numeric-id":2379694,"id":"Q2379694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5573cb072a73745d3dd3f9c7b935353111f490fd","datavalue":{"value":{"amount":"+0.8920424","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":"Q6049083$AA15E743-4EAC-42E3-B04D-FFCD1AA82D2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"582d00148ac1b14e1b5d256370a7ee5770d8b425","datavalue":{"value":{"entity-type":"item","numeric-id":2010112,"id":"Q2010112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d151fe26544b7730f3c28f503fa831d9c8cd72f","datavalue":{"value":{"amount":"+0.89026976","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":"Q6049083$1A10A864-1557-4A68-B284-47CB4521C298","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eaa56587e0eb463f69e639f6ffd268d2a364ef50","datavalue":{"value":{"entity-type":"item","numeric-id":540698,"id":"Q540698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea2a65a4ca86ea19fa111e1e91af3dcf3193b55d","datavalue":{"value":{"amount":"+0.8836414","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":"Q6049083$326F8A2E-40B0-42DF-93B9-A7AF1D3EA2C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92056103dc322323dcb75536ae3f32fc33b16cc5","datavalue":{"value":{"entity-type":"item","numeric-id":2115321,"id":"Q2115321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce71eb259d2ec42a88f5e01be923774226160720","datavalue":{"value":{"amount":"+0.8830997","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":"Q6049083$7A659DC5-4B41-45FC-98D1-76E0B869E351","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a97eff60c1ea07d3607e8e7b28758ba08eae6b2a","datavalue":{"value":{"entity-type":"item","numeric-id":1969763,"id":"Q1969763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cdf7a21a91de72d64836a6610883a39eb01747e3","datavalue":{"value":{"amount":"+0.88139284","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":"Q6049083$B3A395E0-E8CF-4A26-A9FC-86F6F154F438","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"954df9502abd36596cb68cc1112d3834a0091208","datavalue":{"value":{"entity-type":"item","numeric-id":2165261,"id":"Q2165261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"631c3cc07d0646c8a4e4b01ecc344dd1bf02675b","datavalue":{"value":{"amount":"+0.8812478","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":"Q6049083$EEB7A74D-6227-49BB-AA1F-513F4BBAA2EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16dfb471d499934792ee9d3dfafa0f4993e4a1b7","datavalue":{"value":{"entity-type":"item","numeric-id":5131473,"id":"Q5131473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a62dccc201a92edb8130e2c74f6f97e7cc241652","datavalue":{"value":{"amount":"+0.8807501","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":"Q6049083$2981D3B0-8E51-4E7E-A8A3-59256FCBC597","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb8d005e65949ff3526469013e4f61b1d34869c5","datavalue":{"value":{"entity-type":"item","numeric-id":4634530,"id":"Q4634530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b763f7f176797ab342562583c441f188358c04ba","datavalue":{"value":{"amount":"+0.8751579","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":"Q6049083$2A0AF0A9-A5A6-4048-BD42-8D7878848016","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b69989a13070a1806d76031e9aea1f87ebf2966","datavalue":{"value":{"entity-type":"item","numeric-id":2031056,"id":"Q2031056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8acfff54ec84b30b0b06052018ce4c333a16f0db","datavalue":{"value":{"amount":"+0.8743218","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":"Q6049083$AD8CD5DE-081D-4872-9649-BA92BE70CEBF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6049083","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6049083"}}}}}