{"entities":{"Q2205937":{"pageid":2216680,"ns":120,"title":"Item:Q2205937","lastrevid":78419879,"modified":"2026-05-06T11:33:04Z","type":"item","id":"Q2205937","labels":{"en":{"language":"en","value":"An approximation algorithm for the \\(k\\)-prize-collecting multicut on a tree problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7263632"}},"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":"Q2205937$41754FB8-0EEF-4ADD-A192-3E05773EE7A8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5ed3ec405308e32eb01bce6e0d3fcefc9ceb8980","datavalue":{"value":{"text":"An approximation algorithm for the \\(k\\)-prize-collecting multicut on a tree problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2205937$E1AD6ECD-8DEE-40B9-AAA4-6D9A3756E440","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4b87f2a52ded3f36b40102120e774fa632cf7092","datavalue":{"value":"1464.68287","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2205937$37A00746-0F65-4401-A1CD-5BCAFCDBD9B8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205937$2B90076A-DCCC-439A-A971-9026236198C6","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":"Q2205937$95E674FA-037B-45E6-8544-4CCA2F369E90","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"748d3dc0e1ee905f3f3c3b9e1892866fd8648815","datavalue":{"value":{"time":"+2020-10-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2205937$5A3C5A38-21AA-4B8E-8139-CCBE312CD1F0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2205937$9DDA7510-F729-418B-B4C5-5A515484D7ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2205937$1BE83DE4-E105-4F6F-B2B0-8363F7CAB339","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2205937$29947CDD-A4C1-46F0-9026-AFBEA643B19F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2205937$9514AD80-41BA-4622-A007-16DD71AE7F85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2205937$7D86C868-B68D-42E0-B34A-20551EE5C6A0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"560e040b5ff3ebff8b890d7a6b3736f48e86f525","datavalue":{"value":"7263632","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2205937$5FDFB4E1-2D79-427A-AE52-44B4D1B54434","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3888e4321007424eccfc4c0021cff8a7cf7efbc","datavalue":{"value":"multicut","type":"string"},"datatype":"string"},"type":"statement","id":"Q2205937$0749954F-9CA2-4BFE-8639-00663FA9FBE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2f84631ccf9e177417262c1dd6ee88f81ad75861","datavalue":{"value":"\\(k\\)-prize-collecting multicut","type":"string"},"datatype":"string"},"type":"statement","id":"Q2205937$2499E256-52AF-4662-A85F-831AFFABFBD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2205937$9ADF6BAF-A980-4935-8106-D70E47164137","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9b7ba314ae57bab5da9640f1416ba1306391838","datavalue":{"value":"primal-dual algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2205937$4D93526B-4773-4EDE-A195-69DF508C751E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1c837f5c1df41e8e68b7f47e36e18225bb517e6","datavalue":{"value":"Lagrange relaxation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2205937$DD6629A7-3AFF-40B3-BB72-C44149DBFA74","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":"Q2205937$3EB7DFDB-A4E3-4724-8A8E-21818BBDE457","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7b0420e99005422fec5e56350b7a7d898eab318d","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2020.07.014","type":"string"},"datatype":"url"},"type":"statement","id":"Q2205937$B68FB2CC-EB4C-4607-AEA1-D8A93BA7620B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ed3291f1ab9f1bc58d2cf20fa351a8f2a2612967","datavalue":{"value":"W3042489864","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2205937$1F221070-C18B-4077-B48D-A0BA6B9AD669","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"225f6b53ddf025e65f373a0cb3d004c3e9aa0efd","datavalue":{"value":{"entity-type":"item","numeric-id":4537735,"id":"Q4537735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205937$E182ACC2-8AB1-48C4-A2FB-307796B05113","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ef25dcaca47a5224dc8bf68ba789427e2dbeca8","datavalue":{"value":{"entity-type":"item","numeric-id":679443,"id":"Q679443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205937$12DCF2EE-308A-49AC-BDD7-517D859634D0","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":"Q2205937$EDAEF099-36D7-4C9F-A450-45FE407EF741","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":"Q2205937$66E2375B-B286-41F1-A133-252D14A5A5EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b25ff7d43cd4d4c56e78b34ced8d6536f094ba97","datavalue":{"value":{"entity-type":"item","numeric-id":633845,"id":"Q633845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205937$36375B8A-6297-49DF-9EC8-D57CB041761B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2526e4244bcac164b6fb25c8b0353a7f42196f6c","datavalue":{"value":{"entity-type":"item","numeric-id":861281,"id":"Q861281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205937$3598AB8C-4DFC-4506-9ED8-BD52AA389599","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":"Q2205937$59CABDD0-461A-492F-B36C-2D376620CC2E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"54b33414737f75c92effdc0ed172ac6fc1231cb9","datavalue":{"value":"10.1016/J.TCS.2020.07.014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2205937$7E4CD0EB-D0CB-4AFD-846D-12EBE20038F8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a510c9976131fff7debd8cfac5decf0d05c6684","datavalue":{"value":{"entity-type":"item","numeric-id":5425385,"id":"Q5425385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"398d9893c142f019c9923746341bd9d8f3ca4eb3","datavalue":{"value":{"amount":"+0.8615784049034119","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":"Q2205937$34A36039-E0E1-41AE-9E0F-90FF53615E73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bec64e5bb1042b84ca157f81bf4f349144898bd6","datavalue":{"value":{"entity-type":"item","numeric-id":5898483,"id":"Q5898483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"652d62596fc7c75fb25c23f286469808e82d016e","datavalue":{"value":{"amount":"+0.8586809039115906","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":"Q2205937$E913616D-F225-4E3F-A1D6-EDD922982ED7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4b6db09766cb238e6efa42189728de27ce2fab7","datavalue":{"value":{"entity-type":"item","numeric-id":861281,"id":"Q861281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b27ee3df5278d0bd22e2bb60d7d3a0dfc45691a3","datavalue":{"value":{"amount":"+0.8579327464103699","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":"Q2205937$EB826681-121C-4962-B602-F1BD7991C050","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":"c195846fd519b8af3389bea2bdb17ab83e8a24a4","datavalue":{"value":{"amount":"+0.8556150197982788","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":"Q2205937$A9C74858-D780-4D54-81CF-4413E6EABB3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30f5df5fa7446763407fc77999f59848320a7fa1","datavalue":{"value":{"entity-type":"item","numeric-id":423940,"id":"Q423940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e182c0dd82e4c66173d0aad8c32c1f2ddf41559","datavalue":{"value":{"amount":"+0.8174719214439392","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":"Q2205937$10CF9ADA-0860-47B9-AF78-1261C9DD908E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An approximation algorithm for the \\(k\\)-prize-collecting multicut on a tree problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_approximation_algorithm_for_the_%5C(k%5C)-prize-collecting_multicut_on_a_tree_problem"}}}}}