{"entities":{"Q861289":{"pageid":863137,"ns":120,"title":"Item:Q861289","lastrevid":64903386,"modified":"2026-04-11T23:00:04Z","type":"item","id":"Q861289","labels":{"en":{"language":"en","value":"A network flow approach to the minimum common integer partition problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5083806"}},"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":"Q861289$EC04DFC7-F3F2-4627-A5B7-756A14031B35","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dd022ddd6e4c1a11e80fe275793b9fff117f0d4c","datavalue":{"value":{"text":"A network flow approach to the minimum common integer partition problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q861289$CDF01DF6-CB6D-4BEC-93B2-7847B31285DA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2d4df748f05a8a4959c1d9e9d7f52f666be409c7","datavalue":{"value":"1140.68073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q861289$864C61B3-DFD9-47D2-A1C7-EF008563E9A9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1a00148ea6f0fd76199f5f5f7a574069278bff82","datavalue":{"value":{"entity-type":"item","numeric-id":313967,"id":"Q313967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q861289$E8D5B898-A534-42F2-9E88-8417192B09A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0ff69d199b2e4b3f62f192bd9e307ef835b69b5a","datavalue":{"value":{"entity-type":"item","numeric-id":185445,"id":"Q185445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q861289$F1614538-6B37-473B-B70C-25BEC864B887","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dbe93172008deb2a98838e6270fcadcb97a3db25","datavalue":{"value":{"entity-type":"item","numeric-id":630188,"id":"Q630188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q861289$DEDF2AB9-4F02-40B9-80C9-952E85302316","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":"Q861289$BE12FCC5-1177-4BCF-80AB-7C580C0E69F9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b4d2d9af04f3704bbbb24f8b36a1ade40f432b8f","datavalue":{"value":{"time":"+2007-01-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q861289$85DCB135-E543-4A2A-A507-2A203914778D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5faf0641d25f2fa9c82d4ec4f545071f43ed8aaf","datavalue":{"value":"In the \\(k\\)-Minimum Common Integer Partition Problem, abbreviated as \\(k\\)-MCIP, we are given \\(k\\) multisets \\(X_1,\\dots,X_k\\) of positive integers, the goal is to find an integer multiset \\(T\\) of the minimum size such that for every \\(i\\), we can partition each of the integers in \\(X_i\\) so that the disjoint (multiset) union of their partitions equals \\(T\\). This problem has applications in computational molecular biology, in particular, ortholog assignment and DNA hybridization fingerprint assembly. The problem is known to be NP-hard for any \\(k\\geq 2\\). In this article, we improve the approximation ratio for \\(k\\)-MCIP by viewing this problem as a flow decomposition problem in some flow network. We show an efficient 0.5625\\(k\\)-approximation algorithm, improving upon the previously best known 0.6139\\(k\\)-approximation algorithm for this problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q861289$6EA87DA4-784F-4A01-8527-EA8E2010C49F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q861289$E0AABA2D-F129-4CEE-A7B7-6B7D27FDF0B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"16a41880afbd8630e6acc78be050f90ea5608911","datavalue":{"value":"05A18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q861289$5B8693E7-CA51-4A49-950B-666C679171DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q861289$803567EE-9E16-4A2B-BEFA-D10C1B4EF3A0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"73bb2b120bb89134a2c9d8b555cf485a2248e36a","datavalue":{"value":"5083806","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q861289$6FA412B4-BE6F-401B-8712-CB97C25762EB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88be431c04c62de594312511f4fe23998c448772","datavalue":{"value":"minimum common integer partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q861289$6DEF7668-91EF-4F9E-B885-52D18931DC3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q861289$4EDA2833-6FC4-448D-9648-AAAD133F5499","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9527ea6265f63439699edc7d3ec8cd45a55d81c3","datavalue":{"value":"network flow","type":"string"},"datatype":"string"},"type":"statement","id":"Q861289$F56DFCE8-AB32-4F57-A2D1-BF59467627A7","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":"Q861289$FB216F38-B768-4F14-9A3C-FD6759194174","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4b17b8e745419f81dcb0b2217bb2904d0b913f53","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2006.09.001","type":"string"},"datatype":"url"},"type":"statement","id":"Q861289$B396380B-9400-459A-A798-85E73C098F99","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e283b193e8ca9af9f7c27bcd9f5875c878938f05","datavalue":{"value":"W2042185358","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q861289$545899F8-7ED1-4602-8CC9-A48544964C70","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"de762ce4842aef4eb551a3fdee3a22e11bdca0c9","datavalue":{"value":{"entity-type":"item","numeric-id":3434560,"id":"Q3434560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q861289$CCB1A83A-C8EA-4BF4-AD26-E04EF690F3DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bffe48c7c76b90bf68970921698e19786e1600b","datavalue":{"value":{"entity-type":"item","numeric-id":2747613,"id":"Q2747613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q861289$6A9F9495-EB0F-40CA-8DF6-A955E5F1A0A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cbf4343b620ce16a1e6d164688c7cdd174af369f","datavalue":{"value":{"entity-type":"item","numeric-id":3596286,"id":"Q3596286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q861289$E29ED0A5-6A51-4ED8-BEF8-2D16926F51EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d05652188e444fc35e748b68b983451566933e27","datavalue":{"value":{"entity-type":"item","numeric-id":4856179,"id":"Q4856179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q861289$3A9498D0-4393-42B8-B008-9F59DE0D288E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce6133d293bb8bfa149948ffdc9b0f276ef45523","datavalue":{"value":{"entity-type":"item","numeric-id":1186548,"id":"Q1186548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q861289$837F5002-AA7C-4F45-A432-BDE5780C8730","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7a4adea45f991cf5616f7e5b79c2bb9e55e810e3","datavalue":{"value":"10.1016/J.TCS.2006.09.001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q861289$3823A41A-C0D8-4A5F-B1D0-7CCD56010659","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b88161f15a188dd2cb9eec46186fc6e5a9f1a7e8","datavalue":{"value":{"entity-type":"item","numeric-id":3595391,"id":"Q3595391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50bd528b90cfe24249336de5d5d5984d01a4f297","datavalue":{"value":{"amount":"+0.9321342706680298","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":"Q861289$6C6EDB4D-FD3E-4858-8120-2369CCA3FAF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"861c0209cfb0d62951a6f9508a4af161134ea4a4","datavalue":{"value":{"entity-type":"item","numeric-id":4962770,"id":"Q4962770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6bc3dcdf7db6d4d2364b4ead2a40abb9db865e78","datavalue":{"value":{"amount":"+0.9181711673736572","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":"Q861289$F00FAD0B-2B8D-4AC9-AB5C-8A1F6AB80197","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c62ffc9b980db557ff9048b3d99b3fb072d1561","datavalue":{"value":{"entity-type":"item","numeric-id":3434560,"id":"Q3434560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e5e7f71878b3ee56a247e3fe6bca73b2035e0b4","datavalue":{"value":{"amount":"+0.9157400727272034","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":"Q861289$45D8E05A-70FC-48A0-8632-8D5958E7294C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22375aaa2003ffe52f65c892f5204223030edb9c","datavalue":{"value":{"entity-type":"item","numeric-id":2942641,"id":"Q2942641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2784a5150c2c635cccf391a192b0fb6307b8b4b8","datavalue":{"value":{"amount":"+0.8950201869010925","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":"Q861289$5B73A851-544A-4FA3-8E06-2D9EE18E758C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6661f5c7d5376c3a2577bf8855c4807366d73e89","datavalue":{"value":{"entity-type":"item","numeric-id":2051801,"id":"Q2051801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6fa34394db160895cf57aea02b509547984c4b3","datavalue":{"value":{"amount":"+0.8919230699539185","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":"Q861289$E0B1940B-6EEA-46AD-B408-96FD1FB95F8B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A network flow approach to the minimum common integer partition problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_network_flow_approach_to_the_minimum_common_integer_partition_problem"}}}}}