{"entities":{"Q5918502":{"pageid":8049293,"ns":120,"title":"Item:Q5918502","lastrevid":97561337,"modified":"2026-06-05T15:00:50Z","type":"item","id":"Q5918502","labels":{"en":{"language":"en","value":"A 2-approximation for the \\(k\\)-prize-collecting Steiner tree problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7600766"}},"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":"Q5918502$875F8096-5DEB-4850-A6F9-4EA74313A878","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"487bb0622c5b1b3c7edcd1306991b6923f2af9b9","datavalue":{"value":{"text":"A 2-approximation for the \\(k\\)-prize-collecting Steiner tree problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5918502$302A4AFC-799A-4025-A9C9-284E4D0FD3E4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fe9195d05a3fb86356a715f5a7dd3fc104ca4d2e","datavalue":{"value":"10.1007/978-3-030-61792-9_7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918502$1E70B203-C678-4A9F-908F-D44152651712","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a18472ed7d340e0fea5033dd5b7f04dec56d0fba","datavalue":{"value":{"entity-type":"item","numeric-id":329297,"id":"Q329297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918502$73DFB890-1711-4C17-BCE7-5E8D60BA73DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dfe2ee1830efad7b498947b9664dd3316a72a4b3","datavalue":{"value":{"entity-type":"item","numeric-id":2081603,"id":"Q2081603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918502$D2C58DF1-F08C-426B-A07B-8B47036F3981","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b77da03977a479ab8fdf3039ce610e5eead445d0","datavalue":{"value":{"entity-type":"item","numeric-id":5918499,"id":"Q5918499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918502$951C8BA0-61CF-4CD3-AA7E-E96476C40B1D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f63eb77a6cdb61f75205564f776cc43c0ac4bb43","datavalue":{"value":{"time":"+2022-10-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5918502$959D99B9-C9B9-46CE-9346-44B66CEEF29B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ce1d67a7d881f9654023fd91fbf7cf294e32fef1","datavalue":{"value":"https://arxiv.org/abs/1911.09221","type":"string"},"datatype":"url"},"type":"statement","id":"Q5918502$5BE34E0C-0BBC-4BBB-8386-CC1D2E37F519","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f969879f531643f058f8dd4c87a7dd4eb7b8c4c8","datavalue":{"value":"68Qxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918502$7B618AC3-A8DE-4730-B631-CC12374A4DAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1397c7d07b55282862d4db12cbe94becf8137559","datavalue":{"value":"68Rxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918502$14CACBE3-D2E8-454C-81D3-F9518F16F85F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fa684c8d52e9da1094b0c2d762898ace723c7ee3","datavalue":{"value":"68Wxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918502$07B29795-33D3-4355-8B27-8E7EF1657D3A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cddf1471eff03bfe5b4257e84d73b148afdef4de","datavalue":{"value":"7600766","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918502$D2D584BB-E4F4-4A17-B893-D67EB1C82DE2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918502$94906805-A077-4435-A214-D6EFEDE541E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ffd238e03ae4c1f3db822632ad78ac7f8b1bd35","datavalue":{"value":"primal-dual","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918502$A402415F-616C-4FA0-88D3-50D4C7616F1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a6134b66a4318f25fb5d791f819bbd79046d9b9a","datavalue":{"value":"\\(k\\)-prize-collecting Steiner tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918502$9E68CD3C-D005-42FA-BBCC-E313864C1E55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0824f119365205472fb62774c68d0c8925c4cf9d","datavalue":{"value":"\\(k\\)-MST","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918502$B3DB3C6C-3B92-4B9C-B326-3DCE209882C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"078320424038f077fa48d4e6c548a7ca0e5331f1","datavalue":{"value":"prize-collecting Steiner tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918502$5AB5F86E-BBF3-4025-AFDB-25E86269C2D2","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":"Q5918502$B9716BCA-A2A3-43C6-A830-72676F781724","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"443b294f04bac578ffcabfb8e40c9298d8da4242","datavalue":{"value":"W3111415871","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918502$F9482B8F-F27F-4D18-A8BD-0668651C827A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b534e408ec1cdbde0bfa22ef30b8c10c25d137d","datavalue":{"value":{"entity-type":"item","numeric-id":5970779,"id":"Q5970779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dde96b5a9dfbb8be66dbcb1ba889d2f947e1301a","datavalue":{"value":{"amount":"+0.9974069595336914","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":"Q5918502$F748C7AD-76E4-4577-ABD5-F3DFAFDFEB93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9840dbd8fae14435edae3c12b0ab5ffea64019b","datavalue":{"value":{"entity-type":"item","numeric-id":2421447,"id":"Q2421447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0ca9412ff1186d4713677547c88c88fd11750df","datavalue":{"value":{"amount":"+0.918696403503418","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":"Q5918502$41B76AA8-ED17-4E1A-87D4-22D244B2C5CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1d020d3da9cc8d23c406af571beed70f46f569f","datavalue":{"value":{"entity-type":"item","numeric-id":2414116,"id":"Q2414116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0b12714a98ae980ab548bf48791ab54a9dc03c3","datavalue":{"value":{"amount":"+0.9059666991233826","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":"Q5918502$9AE7FA34-08C5-4DFA-874C-8065981A4AEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e55ffbbe0c9884a627b2b02eed6e9fa1d2faa64","datavalue":{"value":{"entity-type":"item","numeric-id":963393,"id":"Q963393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18bccc931bf5a4a9bb102ae8e607fd4a270ba8b6","datavalue":{"value":{"amount":"+0.883667528629303","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":"Q5918502$8F57C8CD-E8EA-4C7F-B4E2-4A0F6F1B6DBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b0e9c6e48ce2bfb46723a5ce46d27290b83d730","datavalue":{"value":{"entity-type":"item","numeric-id":5505663,"id":"Q5505663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"251a2b639fe05c6e43dbfd98ffbd7aebd06f6f75","datavalue":{"value":{"amount":"+0.8815516829490662","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":"Q5918502$F7C65363-957C-4F0F-BF70-7F4F81C3525C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A 2-approximation for the \\(k\\)-prize-collecting Steiner tree problem","badges":[]}}}}}