{"entities":{"Q1893104":{"pageid":1903846,"ns":120,"title":"Item:Q1893104","lastrevid":71086878,"modified":"2026-04-13T19:23:39Z","type":"item","id":"Q1893104","labels":{"en":{"language":"en","value":"A rounding technique for the polymatroid membership problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 769048"}},"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":"Q1893104$DECCDC3A-ED37-4B50-B831-6EAA6AF8DB26","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d090d494a81eed12e7c6d0d9495a41466403baea","datavalue":{"value":{"text":"A rounding technique for the polymatroid membership problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1893104$7D3A5C75-B6E8-47D1-8B45-41D6A4FC9D81","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b7f78390fb1efdca6a95ee55e9aa7860da6f65d1","datavalue":{"value":"0833.05018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1893104$2DD25DCD-54A2-4B86-9E7B-E4EA767DA4BF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"72a2507fadbfdf99b2bfdd758cea94822fe106a9","datavalue":{"value":"10.1016/0024-3795(93)00222-L","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1893104$56561E78-FE6C-4499-AC10-DDA9D4FFE31C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6d542ef6e73cf18fb59380be7bd3211989e9f711","datavalue":{"value":{"entity-type":"item","numeric-id":236333,"id":"Q236333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893104$D62329E0-0050-4A74-B9E3-0F0F17C1079C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8de031de05325b44570d0c47c3ec8813873d565c","datavalue":{"value":{"entity-type":"item","numeric-id":92813,"id":"Q92813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893104$84AA2965-4D85-4CA8-AEBE-8E4C29923406","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"35560ff9834a057879868809cad32ac850730b23","datavalue":{"value":{"time":"+1995-07-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1893104$05826399-1F24-473C-A3BE-CD76D39A097E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bd3a536dda5eccf0dbd8cbf0571548e3ad15cdef","datavalue":{"value":"Let \\(E\\) be a finite set and \\(\\rho\\) a polymatroid rank function on \\(E\\). The polyhedron \\(P_\\rho\\) is the set of all nonnegative vectors \\(x: E\\to R\\) such that \\(x(X)= \\sum_{e\\in X} x(e)\\leq \\rho(X)\\), \\(X\\subset E\\). The membership problem is to determine if a fixed vector \\(w: E\\to R\\) is in \\(P_\\rho\\), and if not, to find a subset \\(X\\) of \\(E\\) that maximizes \\(w(X)- \\rho(X)\\), \\(X\\subset E\\). This paper contains a technique for finding a subset which maximizes \\(w(X)- \\rho(X)\\) over all subsets of the set \\(E\\), where \\(w\\) and \\(\\rho\\) are real modular and polymatroid functions, resp., using as a subroutine an algorithm which finds such a set for another pair of functions which are near \\(w\\), \\(\\rho\\), respectively. This technique gives an \\(O(|E|^3 r^2)\\) algorithm in the case when \\(\\rho\\) is a matroid rank function.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1893104$DB237D03-0B4E-4B44-9CC6-78F6E414C233","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1893104$64029B13-06F0-4025-9AAA-41CA46D45F63","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d7d4745ac19a105cca840a1d73a24006c6a30013","datavalue":{"value":"769048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1893104$DAFCFE11-EE74-45C8-AB51-4FC2666D78A3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9f2a96a2b64089759dd2d2593ced2328c88f9b6","datavalue":{"value":"polyhedron","type":"string"},"datatype":"string"},"type":"statement","id":"Q1893104$683E87E5-1B02-4E3A-BDC7-5D4594DC4399","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a2a5aaf2813613e191091bab6a7937bd2f6db3d","datavalue":{"value":"membership problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1893104$21B55071-2906-404A-AF68-C7106E61CB78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a4c0262f7d70d01c8c5ace8b555790f9b041896b","datavalue":{"value":"polymatroid functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1893104$CF3F2334-E362-4C8C-8E3D-902401D323D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e172629663780e971698d7d841046893adba3be5","datavalue":{"value":"matroid","type":"string"},"datatype":"string"},"type":"statement","id":"Q1893104$61D407B5-988D-4227-906A-B3BD21D994CB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0a7747107654708c9fa9b7dcf2d1aaee3b036d2d","datavalue":{"value":{"entity-type":"item","numeric-id":328587,"id":"Q328587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893104$C9114FE6-6EBB-4E5C-A59A-568C8F8C931E","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":"Q1893104$6B69E667-FA6F-421A-A10F-7A32B941E91A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9cd06c1de98b28ecb0cf1ffcbd9aaf4115d7441","datavalue":{"value":{"entity-type":"item","numeric-id":1056350,"id":"Q1056350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893104$AE58D6BD-A1DC-41B7-B5A6-394C3DD7F1BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f77ede767336323208e2775a5c485c2020357d55","datavalue":{"value":{"entity-type":"item","numeric-id":1104332,"id":"Q1104332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893104$2E7BFCFB-489F-4450-9D75-1C53CD1E4500","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ca8e2226bc49403f5d34bedd57297744e386790","datavalue":{"value":{"entity-type":"item","numeric-id":1168215,"id":"Q1168215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893104$9CB01191-F4A9-4844-BED9-71E43A6A3F44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d076e0530c9c4c069542d85d513880b754633204","datavalue":{"value":{"entity-type":"item","numeric-id":3734185,"id":"Q3734185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893104$56C062B1-8267-4B95-AEF1-2178E15A7793","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f5704113713d5488691e067256f648833fc5a37","datavalue":{"value":{"entity-type":"item","numeric-id":4108358,"id":"Q4108358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893104$F063392C-D942-4365-B4AD-4BA60D377700","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16ee6ba21410efd14ddd2a024a73c0ed4e5a2745","datavalue":{"value":{"entity-type":"item","numeric-id":4111952,"id":"Q4111952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893104$E77EA7EE-ACFB-40E6-B448-02CE22A004A1","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"a6290a390e518187e449bb1289f2bb21d1512dd4","datavalue":{"value":"Q127526107","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1893104$03DC0F88-2278-4362-83A8-E73EE9AC7FBF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ad20e4984623ad072c37d8280830c1816c25c87","datavalue":{"value":{"entity-type":"item","numeric-id":1179434,"id":"Q1179434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8964136058fcd0533cd543586bebb2b6c3612fd3","datavalue":{"value":{"amount":"+0.7984780669212341","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":"Q1893104$9F01C78D-90CF-4795-BC8A-7B9453F963D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b03a9a1f4b4fa7bb0bf5ec9cdd111b46d6cf20a","datavalue":{"value":{"entity-type":"item","numeric-id":1179000,"id":"Q1179000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"177e5c3a3341b0dea85ae129efcb7b594e0813c3","datavalue":{"value":{"amount":"+0.7964850068092346","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":"Q1893104$1785412F-504C-49EB-86D8-B71E20676599","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c7dbb984a6ec042c47b730a47c45beb6a87f4c5","datavalue":{"value":{"entity-type":"item","numeric-id":1410680,"id":"Q1410680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54b2c0be0fdb315a79040f7c680b3b300125ca16","datavalue":{"value":{"amount":"+0.792338490486145","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":"Q1893104$9A32B1CF-1BE0-4E5D-8C73-96B4CFF20F73","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A rounding technique for the polymatroid membership problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_rounding_technique_for_the_polymatroid_membership_problem"}}}}}