{"entities":{"Q5970779":{"pageid":8147575,"ns":120,"title":"Item:Q5970779","lastrevid":102161390,"modified":"2026-06-06T03:49:24Z","type":"item","id":"Q5970779","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 7628944"}},"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":"Q5970779$BC5A3CAC-1BF6-4AA4-ACCB-CAF4030B2001","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":"Q5970779$8826246A-52CA-4114-98F8-ABAB039886EC","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":"Q5970779$76DA70F1-8E6E-4221-87E2-5DD128932BCC","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":"Q5970779$93D61B26-7CCF-4EDB-9D8A-A316A7722B5D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970779$0A90BE84-0FD0-4DA7-99DF-976AA67CC6D4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3ffbf7a5071d227412d80225c3d73ff104ccb41d","datavalue":{"value":{"time":"+2022-12-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5970779$F7F6E119-7D4A-433A-B92A-33EB8D785EDF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fa684c8d52e9da1094b0c2d762898ace723c7ee3","datavalue":{"value":"68Wxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5970779$8CB853F1-11AE-4B4A-8546-54F36C78F1D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f1a97a7188d4143e338e99eba7d65493911702cf","datavalue":{"value":"05Cxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5970779$38D1EEC4-2884-4A25-A65A-319D534FDE7A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c326ad2883b79362eda9e616df0defc4a73471ff","datavalue":{"value":"7628944","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5970779$C64D0CAF-CDB9-4C46-9F73-73007D3832A9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q5970779$0010FAD1-B00D-4CB7-B256-4E350092EC6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ffd238e03ae4c1f3db822632ad78ac7f8b1bd35","datavalue":{"value":"primal-dual","type":"string"},"datatype":"string"},"type":"statement","id":"Q5970779$66322124-EBD9-4ABE-8127-8326D25012D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a6134b66a4318f25fb5d791f819bbd79046d9b9a","datavalue":{"value":"\\(k\\)-prize-collecting Steiner tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q5970779$CB3B2917-9361-4BD9-B469-7859F8D80E2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0824f119365205472fb62774c68d0c8925c4cf9d","datavalue":{"value":"\\(k\\)-MST","type":"string"},"datatype":"string"},"type":"statement","id":"Q5970779$657EB838-46CA-40E3-92D4-18824CA80976","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"078320424038f077fa48d4e6c548a7ca0e5331f1","datavalue":{"value":"prize-collecting Steiner tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q5970779$DED40332-12CC-4D51-BF56-E038851DAB33","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":"Q5970779$DA19D019-BBF3-4A6F-B69C-23BC70FCC027","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8122646b2e88da068646c348618d6f649b288911","datavalue":{"value":"https://doi.org/10.1007/s00453-021-00919-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q5970779$A965E7E5-A71E-46F9-8743-69BB0AC04E71","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f8ce6156c51a0fe9970be64b1a00557a41bd3e68","datavalue":{"value":"W4225489905","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5970779$0053094A-139D-4BDB-961E-FB6C0E08CFC2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc163c03347ae5414a6f1086e8bb9a1ba7911578","datavalue":{"value":{"entity-type":"item","numeric-id":3020008,"id":"Q3020008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970779$855725D6-C95C-4875-AD82-3F6132AC89BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3655a6d523b079eff187c690d3ff3540daa20c9","datavalue":{"value":{"entity-type":"item","numeric-id":2492706,"id":"Q2492706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970779$CC163BB6-9A65-420C-B3C5-79598ABC5017","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e066362ffd854099c35a73c9b12c8851b270733","datavalue":{"value":{"entity-type":"item","numeric-id":293204,"id":"Q293204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970779$4C50E90B-A267-4F8D-AB8C-B319BE7E1712","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e0896c79ee1679be6f42bf3583bd38c8f181bab","datavalue":{"value":{"entity-type":"item","numeric-id":4210146,"id":"Q4210146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970779$8FB2B85E-27DC-4B63-ACDA-79BAD97F7BB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12b20ab46315462d71931a68b1b1d3106c7d1f14","datavalue":{"value":{"entity-type":"item","numeric-id":687042,"id":"Q687042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970779$4684C555-6582-4807-B7FF-6E6768C1B9FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64b5705440d0df1aa971945ffd5418cee404f275","datavalue":{"value":{"entity-type":"item","numeric-id":1305925,"id":"Q1305925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970779$C6865AFA-B165-4E7F-8065-2B60DEB4957C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bebfd564333ed290d4a6aafe28f0eeacfd73e1a3","datavalue":{"value":{"entity-type":"item","numeric-id":5395705,"id":"Q5395705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970779$CB864E08-40CB-40F7-B316-E17B33C77D52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5bcfa757067761b8f8d509efdb8801c6f8515ef8","datavalue":{"value":{"entity-type":"item","numeric-id":1881568,"id":"Q1881568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970779$947C8495-A65D-49BC-8E47-59773D6CEBD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c3d962441425809e5a89b92d7cdfde5d540ea32","datavalue":{"value":{"entity-type":"item","numeric-id":3581401,"id":"Q3581401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970779$AC51BC7C-5A27-48E7-9322-17CEAAD51C54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ac38230d7177643dfa70180c7e73b4f00b3201f","datavalue":{"value":{"entity-type":"item","numeric-id":4834382,"id":"Q4834382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970779$DB847A1B-E0E4-483A-9F2A-DF7DFA7F5B92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbdbcfba4254fa352d776c418fcbeaf2f5872bf0","datavalue":{"value":{"entity-type":"item","numeric-id":2421447,"id":"Q2421447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970779$C873D1AE-72FC-4951-8425-7188023CF948","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf782e57239254752c60a9e2945519e7f4788a8f","datavalue":{"value":{"entity-type":"item","numeric-id":4952698,"id":"Q4952698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970779$A9EADD89-3BC1-40AF-94CC-8E804AD9277D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"531e9b892b59fd88167bdd4beb0925a26df92ee9","datavalue":{"value":{"entity-type":"item","numeric-id":2414116,"id":"Q2414116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970779$7554FF20-6131-40CF-B87A-6CD58915C216","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cccb2aaec1b0fd089776d54d6e7e048a38946578","datavalue":{"value":{"entity-type":"item","numeric-id":4881285,"id":"Q4881285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970779$8C7D7ED8-08CE-4791-8440-E7B1865F7896","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9911c67630a11d4620d825fee38f35fa4cb5829d","datavalue":{"value":{"entity-type":"item","numeric-id":3010438,"id":"Q3010438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970779$CE0A6B4E-B080-415E-9BC2-6C6628E09AC4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1c9d43134f36fd85a3987e5d5feb18018a1554ab","datavalue":{"value":"10.1007/S00453-021-00919-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5970779$F99882D0-D113-48D3-8F0E-E78E3882DFF9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b65c2d63250c297a723f327f103dbf067187b812","datavalue":{"value":{"entity-type":"item","numeric-id":5918502,"id":"Q5918502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ed0d4a8002d98ae475e924c65685a1d36c2409a","datavalue":{"value":{"amount":"+1.0000001","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":"Q5970779$AABA98D0-8160-4AA5-B540-E6037B3C1871","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":"285da9dd4c9f1625343dceee512266a86ccfc146","datavalue":{"value":{"amount":"+0.93499404","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":"Q5970779$AED52770-F8D5-43FE-9C15-5DC91CB88D8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff918f276390cc2152dd82f3cd4088aef7d8c1c7","datavalue":{"value":{"entity-type":"item","numeric-id":2379971,"id":"Q2379971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c7101d307c40a8e5916d7a307c58ccace5fc6ca","datavalue":{"value":{"amount":"+0.9341816","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":"Q5970779$539B55AF-5CD7-48F5-ACB3-D156D1459DDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0a84a4cdecbd54bece158c30d94eda6b39dcdec","datavalue":{"value":{"entity-type":"item","numeric-id":5085996,"id":"Q5085996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c7dfa07f491cd0d504223d118508e7ebaa575434","datavalue":{"value":{"amount":"+0.9339093","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":"Q5970779$96E532C3-7986-4C6A-99FA-0F10C001EC02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ec6658c00ff55121cd825cf95cf1a8cd9d6165d","datavalue":{"value":{"entity-type":"item","numeric-id":5369504,"id":"Q5369504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2786f43ba4788ec7efdfd5af286cfb6b9a55c148","datavalue":{"value":{"amount":"+0.9309418","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":"Q5970779$A8C525C7-0CD1-48BB-814C-F0C3F3D3BCB0","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":"d0e92e5c8d5680d5bf637fc79a087e13cfcc9187","datavalue":{"value":{"amount":"+0.93015796","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":"Q5970779$A76FC31F-2999-46FC-8CEC-5BCD477CE86C","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":"7f429adcb38c95beb5ce3e6a69ac16729a7e723d","datavalue":{"value":{"amount":"+0.9301579","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":"Q5970779$B9832552-C388-46BE-B7B7-EACF157720C9","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":"e221cbfed739579743bdc614448cc4f1899fef0c","datavalue":{"value":{"amount":"+0.92930436","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":"Q5970779$CA577EA5-186E-4D04-B557-91B12C5A2080","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01c55fd8aa2ef19846f96a9fbff7e5c446c2830a","datavalue":{"value":{"entity-type":"item","numeric-id":5171192,"id":"Q5171192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e672db46a6a85936c3dcd7a14c595056cbb8509e","datavalue":{"value":{"amount":"+0.92925376","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":"Q5970779$F0678B85-D161-4D35-B9D1-2A0CFE24E99C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"836004b6729d8ddf61f9b05fb9cc38d0f057fc14","datavalue":{"value":{"entity-type":"item","numeric-id":3020008,"id":"Q3020008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c5fd25516429b44ff461f8b97867e21ca4a06f9","datavalue":{"value":{"amount":"+0.9292537","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":"Q5970779$1F947589-B368-4623-9236-C773681DB3CF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A 2-approximation for the \\(k\\)-prize-collecting Steiner tree problem (scientific article; zbMATH DE number 7628944)","badges":[]}}}}}