{"entities":{"Q1850585":{"pageid":1861327,"ns":120,"title":"Item:Q1850585","lastrevid":55946581,"modified":"2026-02-21T10:02:25Z","type":"item","id":"Q1850585","labels":{"en":{"language":"en","value":"A fully combinatorial algorithm for submodular function minimization."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1843809"}},"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":"Q1850585$26FB942D-8762-49A7-8C8B-E42B711DD617","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c001c82929eebed37ea29f721d6c4b344c8ad897","datavalue":{"value":{"text":"A fully combinatorial algorithm for submodular function minimization.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1850585$92BAA2CD-D1DD-4996-86E3-4E0AE883154D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0981e324904e2b65647d43d4ff0a180c2de59373","datavalue":{"value":"1175.90332","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1850585$C324DAE3-715B-48FF-AD48-986F07BB038B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"17597b30db72c4c5d242850baa1f212800adb33d","datavalue":{"value":{"entity-type":"item","numeric-id":185376,"id":"Q185376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850585$306CBD85-8905-4DF9-9A78-FB41420841D9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850585$F6443989-BC46-410C-8818-FBF3AC699C91","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"41f50e6d48cb83c0777ccfeab26a53b6ee6f8dc2","datavalue":{"value":{"time":"+2002-12-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1850585$7046D773-9632-459F-85E1-9BC18989E788","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f89e8f3fd05c8b93acabd6a1e3333fc28c2331cf","datavalue":{"value":"Let \\(U\\) be a finite nonempty set of cardinality \\(n\\). A function \\(f\\) defined on the subsets of \\(U\\) is submodular if it satisfies \\(f(X)+f(Y)\\geq f(X\\cap Y)+f(X\\cup Y)\\) for all \\(X,Y\\subseteq U\\). The author, \\textit{L. Fleischer} and \\textit{S. Fujishige} [J. ACM 48, No. 4, 761--777 (2001; Zbl 1127.90402)] and \\textit{A. Schrijver} [J. Combin. Theory, Ser. B 80, 346--355 (2000; Zbl 1052.90067)] have developed, independently, combinatorial strongly polynomial algorithms to minimize submodular functions. These combinatorial algorithms perform multiplications and divisions, despite the problem of submodular function minimization does not involve multiplications nor divisions. Schrijver asked if one can minimize submodular functions in strongly polynomial time using only additions, subtractions, comparations, and the oracle calls for function values (this sort of algorithm is called fully combinatorial). In this paper, the author settles this problem by developing a fully combinatorial variant of the Iwate, Fleischer and Fujishige algorithm.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1850585$AAFDEA20-5702-46C9-A22F-209ECEE07CA2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1850585$B22BB49E-F4CF-45FA-BC30-9B8522FB856A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1850585$663C7FEB-E273-43C2-B5FF-6751DD22513D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a76ba32477641dbc5c2a6ab2973e0388b6bf3492","datavalue":{"value":"1843809","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1850585$03C4EFCE-DF51-4362-91A6-4AAFE1E3F926","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d9b6b6dbccf408ae27bec118c5bdf5ed397ea7c3","datavalue":{"value":{"entity-type":"item","numeric-id":490924,"id":"Q490924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850585$A06BCB6F-66F5-4041-BB8F-000CE1B1C921","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":"Q1850585$E8B30722-09FF-468B-ACA7-66F1C8A8ADA1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e36d19f7a61e99ffe395ec15635bcdf0f93453e6","datavalue":{"value":"https://doi.org/10.1006/jctb.2001.2072","type":"string"},"datatype":"url"},"type":"statement","id":"Q1850585$CEE7551E-EC74-4B51-B9D3-CF3310F601AF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"858480250120b7b61eff15d32039a24eca589c6e","datavalue":{"value":"W2585238812","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1850585$03326973-CEAB-4772-A16A-371CA5966E0C","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":"Q1850585$787CB66C-6503-473C-86DC-D63BD2A608D8","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":"Q1850585$C9F5D50C-2785-44D5-B968-B68D1A300212","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb97aa0ae022d4dc38b27f53ae16228cc4072891","datavalue":{"value":{"entity-type":"item","numeric-id":5684698,"id":"Q5684698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850585$8DEFBEF4-14AB-4DF9-B163-6B49C27E90E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58d9aab9a6f0558cb5d121779b1d8592d7bc31d9","datavalue":{"value":{"entity-type":"item","numeric-id":1600097,"id":"Q1600097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850585$221667A5-B298-4AC7-87C7-A54447F54CC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b71956cbfa836f94d8d1ed2cac40cd4173b1d49","datavalue":{"value":{"entity-type":"item","numeric-id":1116889,"id":"Q1116889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850585$6EDE108B-0404-4097-8EA9-0D212CDB4ECD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a7de05208a028acfde9f78fc58733a1deda9bf4","datavalue":{"value":{"entity-type":"item","numeric-id":3731344,"id":"Q3731344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850585$97782082-5314-4B05-A538-E5C3597C03ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33a1c30aba5ada8564ff4d14a3fa87bff203e9e2","datavalue":{"value":{"entity-type":"item","numeric-id":1188800,"id":"Q1188800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850585$9BCBEE31-B314-4103-8684-FEF1E7ED28E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4b24afdc559d4dfafb8f042dc340fb9b4e2b9e4","datavalue":{"value":{"entity-type":"item","numeric-id":3313913,"id":"Q3313913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850585$982F095F-ADD8-4B34-B877-2B345801A1D5","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":"Q1850585$2C11C1AD-EEAC-455C-BE09-A51EF2AC0A05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d16b4d29c0ba31b1bc8e06218af428a76fc8ce67","datavalue":{"value":{"entity-type":"item","numeric-id":1210712,"id":"Q1210712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850585$3D41BBC7-E847-4D24-8843-AC7459FF4534","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a782baf98527296436203e217bc3fcaa2c626b18","datavalue":{"value":{"entity-type":"item","numeric-id":1363412,"id":"Q1363412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850585$3514EDF4-51F1-4C90-B2E9-0275C1CC3194","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4e5a50e1e90aeb19ca4ff2b3971a69ace23d33f","datavalue":{"value":{"entity-type":"item","numeric-id":3682236,"id":"Q3682236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850585$27C81B24-E672-41A3-930E-3E30F6F8C675","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d575657fa68b8ef0feca63f02ca1b0b6990f89b9","datavalue":{"value":{"entity-type":"item","numeric-id":3989010,"id":"Q3989010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850585$AB05FAFF-AAD6-40E9-ABF5-120E6BD08262","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"401908d0fd5c7917498fc9a7adc7050a8168874e","datavalue":{"value":{"entity-type":"item","numeric-id":1290631,"id":"Q1290631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850585$71C320CD-21FF-4A3F-8FA4-46E21DDD6E49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b42f01619235047e4cf6362bf5725564c6284fe","datavalue":{"value":{"entity-type":"item","numeric-id":1850505,"id":"Q1850505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850585$A95FC796-A1C0-4C7C-9E60-3877762F66CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95b664b422d432de07664d1d76dfbfff62150adb","datavalue":{"value":{"entity-type":"item","numeric-id":2547868,"id":"Q2547868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850585$73189B37-C5B6-411C-BF38-9FF12C6FA2F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18896b12fcfc75b1384ddbb4d217a7db3a02e745","datavalue":{"value":{"entity-type":"item","numeric-id":1079110,"id":"Q1079110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850585$935FB7E3-64E4-43FD-AF6B-874670AC2B2B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cb298a1c5e4d7e93a4d6135c93711b6e5281d168","datavalue":{"value":"10.1006/JCTB.2001.2072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1850585$A7D88FD2-A65B-46A8-A465-BD1D924BD9EC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8cd6f2380377e6fdddf90e1537754f8750905369","datavalue":{"value":{"entity-type":"item","numeric-id":1850505,"id":"Q1850505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8017f292b5c1add2ca76319a35a48be7c5950e7f","datavalue":{"value":{"amount":"+0.8976549506187439","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":"Q1850585$B7EC925F-38B4-4098-927B-A06966BE77FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"259406fb7a209e0df3abf3b33ffeca6c954f83da","datavalue":{"value":{"entity-type":"item","numeric-id":4633938,"id":"Q4633938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5dd1f2712148e1d3444a43691e78b7ee9a1a425a","datavalue":{"value":{"amount":"+0.8921790719032288","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":"Q1850585$512EFCCA-C8A0-43F8-968F-844FF577652B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5792a15920836b27abdaf65cc010f7ec67c2b736","datavalue":{"value":{"entity-type":"item","numeric-id":4886038,"id":"Q4886038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43e7351e32eacf578c91854bb15adfce9f7e0175","datavalue":{"value":{"amount":"+0.8746321201324463","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":"Q1850585$252005D9-AA92-41CF-965E-F645148BA3B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"525fd17e935b64aa83d011b86e47a157b8a990ba","datavalue":{"value":{"entity-type":"item","numeric-id":1290631,"id":"Q1290631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5dd756797067ae2f9133ac7f3ac77896aac26691","datavalue":{"value":{"amount":"+0.8732792735099792","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":"Q1850585$1BCBA838-836B-499E-BE3F-2307EE6A972B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1850585","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1850585"}}}}}