{"entities":{"Q1035686":{"pageid":1037534,"ns":120,"title":"Item:Q1035686","lastrevid":50804234,"modified":"2026-01-15T05:58:22Z","type":"item","id":"Q1035686","labels":{"en":{"language":"en","value":"On the minimum hitting set of bundles problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5624935"}},"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":"Q1035686$438356FC-0035-4D82-B434-FB84058653A7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1abe2b811bdbd38f69a775886cad21b16494a07b","datavalue":{"value":{"text":"On the minimum hitting set of bundles problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1035686$EE8F1619-1926-4911-9AB1-7507AF4E5E7F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ba40b1c25f73e848c277ff489919f85f2913e703","datavalue":{"value":"1175.68557","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1035686$A7A37960-987C-4986-B97E-EF427834ABF9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5be5acf0a8011cc88d03bf15153b5a35f31f9b7c","datavalue":{"value":{"entity-type":"item","numeric-id":278713,"id":"Q278713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035686$1ECC98D7-643F-4380-A2CF-379B876CA141","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ccf1b2b72f1d517bbb25e441589a89c7a2462790","datavalue":{"value":{"entity-type":"item","numeric-id":398883,"id":"Q398883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035686$8EF5DC3B-8CC8-4102-A94D-AD688302A490","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"345b25bc623291cd2276fcb97b577e8382e54f57","datavalue":{"value":{"entity-type":"item","numeric-id":396663,"id":"Q396663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035686$E62FE11F-62B6-4472-A23D-BF9996DDA6DF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035686$5BB00367-49FA-44F1-AC22-44BD070BBB41","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ef2b4a391107c8565fc25ba0caa09f7f59741046","datavalue":{"value":{"time":"+2009-11-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1035686$E0A311D0-A177-4331-A11F-3210DEF4EF3A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"81b61395eb918d9d7dda4d9e8d62b2baae9bb90c","datavalue":{"value":"https://basepub.dauphine.fr/handle/123456789/2149","type":"string"},"datatype":"url"},"type":"statement","id":"Q1035686$582DB109-DD30-4BEF-A2D5-A83C1A4F5B97","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dbd8a19fa7a08caa6badc89948a847201120ebea","datavalue":{"value":"An input of the minimum hitting set of bundles problem is an set \\(\\mathcal E=\\{e_1,e_2,\\dots,e_n\\}\\) of \\(n\\) elements with non negative costs \\(c_i\\) for \\(i=1,2,\\dots,n\\) and a collection \\(\\{S_1,S_2,\\dots,S_m\\}\\) where \\(S_i\\) is a set of subsets of \\(\\mathcal E\\). The aim is to find a solution with minimium total cost where a solution is a subset \\(\\mathcal E'\\subseteq \\mathcal E\\) such that for every \\(i=1,2,\\dots,m\\) there exists \\(b\\in S_i\\) with \\(b\\subseteq \\mathcal E'\\) and the total cost is \\(\\sum \\{c_i\\mid e_i\\in \\mathcal E'\\}\\). There is given \\(N(1-(1-\\frac 1N)^M)\\)-approximation polynomial time algorithm where \\( N\\) is the maximum number of subsets of \\(\\mathcal E\\) per set and \\(M\\) is the maximum number of sets in which an element can appear. The scheme of algorithm is classical but the approximation ratio is the best one. Relation of this algorithm to similar problems is discussed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1035686$D77E10DC-A55C-41D0-88D7-37CB0F584ED2","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e77d710fff360ac5f5e834555bc2a388abb806e6","datavalue":{"value":{"entity-type":"item","numeric-id":409252,"id":"Q409252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035686$B8A6FFD6-088E-4B8A-9E7F-B876877F1B5F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1035686$A1007CAF-BE09-4A0A-8260-27FBCC95AA2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1035686$BCA5677E-9FF9-4F5F-A952-F4AB0BD19688","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1035686$158AFA72-FEF5-491F-BC8F-26F907791DD1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4d3f30d8fc9423520f9197c5bd1d534a3c60b42d","datavalue":{"value":"5624935","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1035686$4672F507-621D-429C-8C31-4AAE70DB39A9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"006e80d85da9ccca77e14ee4460b5f70ee1c8b83","datavalue":{"value":"minimum hitting set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1035686$F69CFF58-52CC-4BE1-917F-751F4882AF19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bec68cf20a321a392cb3de44e08fa2f355172d5b","datavalue":{"value":"min \\(k\\)-sat","type":"string"},"datatype":"string"},"type":"statement","id":"Q1035686$903E0E8A-2998-46F2-9176-8A353E3B724A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1035686$C3D53CBD-208A-479C-8FD5-9A7893A55630","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":"Q1035686$5CA12E5D-E93B-4195-A373-F5F2EC607AEB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"edc317d10bd20a37a5dff40f6436b6504c92bb26","datavalue":{"value":"W2786382671","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1035686$29D9E984-D74E-492A-884C-326180622DFC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9dc4dc8695aaa4d0ec31340b16f1901c662b5229","datavalue":{"value":{"entity-type":"item","numeric-id":1143173,"id":"Q1143173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035686$59325E65-1BF5-4A1F-9CFA-B708DB19CF25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebc8041862aa532bbba369a057626a7082bb0fe0","datavalue":{"value":{"entity-type":"item","numeric-id":1780843,"id":"Q1780843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035686$4F71BF0B-934B-4905-9E4A-735DAFB87C93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1fa370e6f287c9409825338bda317710d7ead802","datavalue":{"value":{"entity-type":"item","numeric-id":1306458,"id":"Q1306458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035686$992F5C6C-7F3C-486D-8AF1-267BB07F44F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"732183f38719a5ffc0fae37c8e2ad20d7e91a145","datavalue":{"value":{"entity-type":"item","numeric-id":3581279,"id":"Q3581279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035686$0A768B74-35DE-4F8F-8E76-6005DB86C10F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a085110f25069146b2ebfef0f9dedd979d8f36a1","datavalue":{"value":{"entity-type":"item","numeric-id":3579199,"id":"Q3579199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035686$5614B568-AD06-4A48-AF58-7014ED7E2D98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd40e76594a43720fae74f641ef5b271afa3c125","datavalue":{"value":{"entity-type":"item","numeric-id":3149886,"id":"Q3149886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035686$8C2030B1-AD04-4F7D-AD3C-597ED2109EB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11d8af2df779085adeca485e2691445d9b764369","datavalue":{"value":{"entity-type":"item","numeric-id":4296521,"id":"Q4296521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035686$672CE41A-FC8B-4F26-BBD8-1BB88902C337","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d30ec572585cf4b40178401f51be4fda2291a102","datavalue":{"value":{"entity-type":"item","numeric-id":1351157,"id":"Q1351157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035686$620A7A14-8490-419F-9459-00F468799853","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc3cd2c91bb9432d0a84af812fa4721a860fbf27","datavalue":{"value":{"entity-type":"item","numeric-id":834926,"id":"Q834926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035686$596DBB54-0795-4198-9AC6-73ECD9C3C36B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a20d09513baf32113955ba3ecf79c8e2d6ab34f2","datavalue":{"value":{"entity-type":"item","numeric-id":3512428,"id":"Q3512428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035686$DDDCDF50-3324-4ACC-9E8C-254A8CFBE6FA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8fe161fdf355b8b42155aaa331a1140d9f6a7114","datavalue":{"value":"10.1016/J.TCS.2009.08.017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1035686$514D07FC-D551-4AC6-AB69-276DA1A23C01","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"420365d7bbbfe2cf58b83de615ae22185dfcc1cd","datavalue":{"value":{"entity-type":"item","numeric-id":3511409,"id":"Q3511409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44de95975ba38b33d7fd3fe51b993899622f3ea3","datavalue":{"value":{"amount":"+0.92398601770401","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":"Q1035686$004290AC-20C4-4814-88D4-9B6BB13E404F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"71ce3ce928203b9e59a0f2ebcde0415dac9bb435","datavalue":{"value":{"entity-type":"item","numeric-id":2344004,"id":"Q2344004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a275c59a639cfcc0f4fa2279e874c8781a3b796f","datavalue":{"value":{"amount":"+0.75396728515625","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":"Q1035686$53CBBDC2-91F3-47B9-A53A-36E8AD1814AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a9df9a93367cfcf5e715ac5fede454b54a6b7c20","datavalue":{"value":{"entity-type":"item","numeric-id":876698,"id":"Q876698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1b3dd43dbd146617954d281874fb4c6a24a58fb","datavalue":{"value":{"amount":"+0.7463120222091675","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":"Q1035686$4AE7015C-18D7-4549-982C-15BC65CB185A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7101b3c5276bbc4050b6f3935264280ccb978951","datavalue":{"value":{"entity-type":"item","numeric-id":2429345,"id":"Q2429345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"973b0f4da93a505689a91a52cfb616d986c033a7","datavalue":{"value":{"amount":"+0.7405529618263245","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":"Q1035686$E39E10EC-8B0C-49AC-858C-91219A0ADCE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f89dc3b14b0b66c2afc9c91298b2f5358526b28","datavalue":{"value":{"entity-type":"item","numeric-id":5370696,"id":"Q5370696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1bc6e37ae7dd8c95617a0510dd5592b8fc33b57","datavalue":{"value":{"amount":"+0.7387888431549072","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":"Q1035686$D60A8785-A3CE-4880-9F14-0D8545E67E55","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1035686","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1035686"}}}}}