{"entities":{"Q1082267":{"pageid":1093019,"ns":120,"title":"Item:Q1082267","lastrevid":48982330,"modified":"2026-01-06T09:50:00Z","type":"item","id":"Q1082267","labels":{"en":{"language":"en","value":"A fast approximation algorithm for the multicovering problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3972645"}},"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":"Q1082267$DC011E64-BD43-4893-99CF-B1CA4C224A7A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e172c1edf5a4134d74c07747e90ee2d2205905fd","datavalue":{"value":{"text":"A fast approximation algorithm for the multicovering problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1082267$05E7A015-6652-48F2-9C3E-B6A2AD6051C9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7fcb1404c2c8637ad2a059641d9e9a988ac17201","datavalue":{"value":"0602.90110","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082267$CBE489EF-7F59-4B19-8980-E161C54C2EB2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"81faa6e9b5430f9013df75a696e87bdcf13e193b","datavalue":{"value":"10.1016/0166-218X(86)90016-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082267$C6F19DB4-6717-4E8C-8A90-522A0BAE69FE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0983e0688b2ebfdef46f56e43c556cd29449983","datavalue":{"value":{"entity-type":"item","numeric-id":284834,"id":"Q284834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082267$CFC416D9-F25A-4DA7-B3FF-847A8859FE4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5b969806e15667b8bb837290cff38032bdae579d","datavalue":{"value":{"entity-type":"item","numeric-id":242829,"id":"Q242829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082267$DB0FDC21-D460-4E90-A15A-7673DF82FC6F","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":"Q1082267$540F8F9B-019C-41C1-B060-F56807C9D8D8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1082267$9F3919CA-54FF-4DC9-BE03-6906E36605AD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"db3482b0e3bcd0b0e87380e66c735afc953839f0","datavalue":{"value":"The multicovering problem requires to find the (linear) least total cost for a group of sets with the assumption that given elements are covered at least given times by elements of the group. This problem is NP- complete.    The paper gives an algorithm which uses O(max\\(\\{\\) n,m\\(\\}\\cdot n)\\) time, where n is the number of prescribed sets, and m is the number of elements to be covered. The coding of the algorithm is very easy.    The paper contains a sharp bound for the ratio of achieved and optimal cost, the example can be easily received from an increasing group of sets.    One can ask for the probability distribution of the ratio. This is interesting because of the fact that the bound for the ratio is painfully large.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082267$DF14BDA0-2AAC-4243-BD14-C001EE8A802D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082267$B31132B5-A67E-4824-B4B1-6EDB7A053ABD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082267$14DCE65F-1DE6-4E3B-B33A-63E3137CFF41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082267$F94C910E-B9FD-43C7-9DC2-98837CA98332","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6958ea3363ca9244e0da0201efd237a8410f9a0c","datavalue":{"value":"90C09","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082267$09FCAB69-F9B8-4832-9F06-531AD214DCFA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ea88d466ce29057566a4fedd8d5bfee81a03f21c","datavalue":{"value":"3972645","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082267$AB4B8AD9-2450-4C72-BE62-0EE92E193D20","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082267$B282A834-D525-47B5-9AC0-DE1C24B4A1D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f641bd239fe6f0d5fb2cc0d2b3f89cbc609bab87","datavalue":{"value":"heuristic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082267$1E5F6C68-52DB-43AF-A3C2-D475418EA421","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"edba685c71772380417bcbc99abe795ba8c0ebd3","datavalue":{"value":"multicovering problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082267$F1F28445-D9DA-4A59-BA7B-0C50C415D86A","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":"Q1082267$4C012682-ED63-418F-9E84-E6D61EABB6D8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0411a384efe8f871835c9d52a082ddc67162974","datavalue":{"value":{"entity-type":"item","numeric-id":3910012,"id":"Q3910012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082267$D793CBD8-3713-4A47-878C-7539DA51B819","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e1e3627f13890a3338bad7f8ce5235036336ff8","datavalue":{"value":{"entity-type":"item","numeric-id":3964325,"id":"Q3964325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082267$183A1520-1A1B-480B-A341-A598539A8A60","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":"Q1082267$F08B04A4-0DDD-4EAF-A64A-C3C81F026CA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00a9e252dcd967174efec124226bbf4f16c443d8","datavalue":{"value":{"entity-type":"item","numeric-id":3947140,"id":"Q3947140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082267$450A843B-2222-4F83-9B77-59DC906A8A84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a664596b502fa9850f7c77f584cc2be31c495e62","datavalue":{"value":{"entity-type":"item","numeric-id":3342591,"id":"Q3342591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082267$1F92C3B6-AA1E-4BAC-94A6-1CF02B46C36F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e8671cee9f3387b05a8df92d86eddb6b330f69b8","datavalue":{"value":"https://doi.org/10.1016/0166-218x(86)90016-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1082267$E811910E-B833-41BA-8D9A-EAC9DC81D54C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fe6a0d862a78f21d74455ea9e73c08d93ce865d3","datavalue":{"value":"W2069870307","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082267$FDA763CA-D0E3-48C9-B6C7-5AD15B1669C8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be5b73627f8b35aa69c84b4b182d1527b8ec16ab","datavalue":{"value":{"entity-type":"item","numeric-id":1205691,"id":"Q1205691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"970ecbb5c3db2c41f09efb13ba7ffaaddfe6e7cc","datavalue":{"value":{"amount":"+0.8369783759117126","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":"Q1082267$5DB20CAF-B60A-42E8-9B7A-AD72FBEA5CF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a7502991d4b31348933d9caeb134e677ea16a7c","datavalue":{"value":{"entity-type":"item","numeric-id":1312032,"id":"Q1312032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f24171d7fb4a0a373bf675258662ebd9659f3522","datavalue":{"value":{"amount":"+0.8089501857757568","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":"Q1082267$99B2022D-27ED-4DA4-8BA0-DC69B9B38282","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4aae8d9f6e497b5869f96e0ec72e21af14b191d","datavalue":{"value":{"entity-type":"item","numeric-id":837180,"id":"Q837180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f24171d7fb4a0a373bf675258662ebd9659f3522","datavalue":{"value":{"amount":"+0.8089501857757568","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":"Q1082267$0A944A64-1AD7-4460-8940-124A500462D5","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":"ff7bd2df39a22e2d9a41e6c0424ee17c19128f94","datavalue":{"value":{"amount":"+0.8064851760864258","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":"Q1082267$F5E748FB-3C65-45DD-B1E9-CD6A96AE7117","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":"86deb9002285e0b483983db716b7e20895109d64","datavalue":{"value":{"amount":"+0.8004805445671082","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":"Q1082267$A39AA20D-CAFE-4E0F-A8C4-0A0ACB511A52","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1082267","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1082267"}}}}}