{"entities":{"Q5951962":{"pageid":8128764,"ns":120,"title":"Item:Q5951962","lastrevid":47720539,"modified":"2026-01-02T12:53:26Z","type":"item","id":"Q5951962","labels":{"en":{"language":"en","value":"A strongly polynomial time algorithm for a constrained submodular optimization problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1687488"}},"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":"Q5951962$DB0B99E9-FD66-4A31-A62A-E5CB4F20EDFB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"421e7054176b4c6d39c4c4098635d73549c1fa1d","datavalue":{"value":{"text":"A strongly polynomial time algorithm for a constrained submodular optimization problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5951962$68230122-4945-450F-AD3D-43BD93E09BA6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3d5b6bde26c72a2471c88a21200f6e3ea2d5bd4b","datavalue":{"value":"1086.90049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5951962$3B9B228D-D6B8-4777-9195-B49EE63318A1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6f49c04c11d84de43d65648d432752c237aca275","datavalue":{"value":"10.1016/S0166-218X(00)00285-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5951962$7A2E8ABE-C9C4-4FC9-BDE4-0DC1D54F1FDE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ff1ef44ac9a32152a02c08533e57178afe095060","datavalue":{"value":{"entity-type":"item","numeric-id":1103513,"id":"Q1103513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5951962$4A0FA62F-D5E3-45C0-BF07-B8A3727FFF99","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5951962$9F74E022-65F4-41A9-B96F-01B55DA63D5D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d6f630a8f9062cc7a61bf0b0d4072e8f242af2b3","datavalue":{"value":{"time":"+2001-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5951962$E22733D5-2E6B-4A11-A2E8-FC9F342308B2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7b37f5580251d8404198347bfe47d852d93c823b","datavalue":{"value":"The author [Math. Oper. Res. 23, No. 3, 661--679 (1998; Zbl 0977.90073)] presented a weakly polynomial time algorithm for the problem of optimizing over the intersection of a submodular base polyhedron and an affine space (when the number of constraints describing the affine space is bounded). This paper contains a strongly polynomial time algorithm for this problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5951962$907DB752-AF12-4AE3-86E2-79E6EFB181BC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5951962$5EFFBC81-1C9E-40C2-ADFA-262B2B2D8726","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5951962$C31EB733-C496-45DB-A0ED-060F2773474C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5951962$925746F3-9693-4484-9BBA-826EE0243767","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5951962$EA551AF8-934E-4AF8-B52C-C2850018D61C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5fcf4e8e48cb838064840457cb122407883e9c36","datavalue":{"value":"1687488","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5951962$7B283588-00E5-474A-8F47-D5A8F84DFEB4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f53eb6ebf7e67d492b6251d54357257e1d4f26d","datavalue":{"value":"Submodular function","type":"string"},"datatype":"string"},"type":"statement","id":"Q5951962$2476D932-9E3A-4F47-83C4-12B45E7976BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"438221a1f23584328ed4b3a87670719541313572","datavalue":{"value":"Base polyhedron","type":"string"},"datatype":"string"},"type":"statement","id":"Q5951962$45B3CAF8-6B21-4962-803E-E92B6DF0E89F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b5256a4dbf9140e9cbeb64e5c3c54b5d18a42cdb","datavalue":{"value":"Max flow","type":"string"},"datatype":"string"},"type":"statement","id":"Q5951962$8A16B471-4AD0-4099-B378-27D9920F22B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"46531e54e318c2319f718ce2252f187c7b8decc9","datavalue":{"value":"Min cost spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q5951962$8CE01563-CECC-4D58-8695-CC38F1AEADF8","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":"Q5951962$5D86E9E5-A339-4F39-B54C-8E35B60F14A7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"500fe8c19d0d24fbfe5f0fac731db81b7f692176","datavalue":{"value":{"entity-type":"item","numeric-id":4177292,"id":"Q4177292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5951962$A8C83BE1-7D1B-44D7-97F2-158D20AC0A76","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":"Q5951962$6476275C-5BC5-41D1-AE9F-CFA621D9846E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"854bf29386092635a477e0881f3f0c76f5ed2664","datavalue":{"value":{"entity-type":"item","numeric-id":5624995,"id":"Q5624995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5951962$CE6DE54E-15D0-4D01-8A01-D92E6B95F708","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":"Q5951962$A63FF9A7-8CD9-4F78-8693-0ECC05D6E00A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da5b18e5a44e3c67c75b0887be40e31fe6fc87d6","datavalue":{"value":{"entity-type":"item","numeric-id":4080986,"id":"Q4080986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5951962$3A1CF628-1449-4C60-9D58-DF515D34EB82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a9df03d940bbd4c025d80e4f6d96f2a49bffb4fd","datavalue":{"value":{"entity-type":"item","numeric-id":3237973,"id":"Q3237973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5951962$C0E75CE8-A445-4C69-9A82-49BBC3EAC3F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fa3614158d449cf105bf6609faf76182d9711da","datavalue":{"value":{"entity-type":"item","numeric-id":3747243,"id":"Q3747243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5951962$1A77D551-675F-4506-939E-047EA3C746D7","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":"Q5951962$32757FA2-17A6-4BA1-836C-127752ABF366","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5827f77ce2945db40418bd6aebd2cb7e89cc64fb","datavalue":{"value":{"entity-type":"item","numeric-id":1803612,"id":"Q1803612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5951962$B4FFAEA9-A3B6-4BE4-B5AE-49EA32D18B60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1e8c7fb5fae200c0ed14d43c4bd9bc65b15cdb0","datavalue":{"value":{"entity-type":"item","numeric-id":2757558,"id":"Q2757558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5951962$728D8E7B-71FE-44BB-AE7B-D21B8A0F9FFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fce002855ae31e48173fa9c9618b0c871228bfff","datavalue":{"value":{"entity-type":"item","numeric-id":3941156,"id":"Q3941156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5951962$80F46AA5-6193-47C5-B582-6B745919411D","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":"Q5951962$AC867963-AE45-40F9-9F7E-BA2FA1E667FA","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":"Q5951962$34A16652-F182-4C1A-B680-C82C99E85705","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"878c4568bee16da00e5571c2c10b5694f8382ce0","datavalue":{"value":{"entity-type":"item","numeric-id":581206,"id":"Q581206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5951962$3ECCFCD1-3ABE-4A08-AEC5-0C140449349C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8cacfb96d5aca2b660febcc903f516ecf906a769","datavalue":{"value":{"entity-type":"item","numeric-id":1908017,"id":"Q1908017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81496d1eb406fd8af2528a170d242006c10bc99d","datavalue":{"value":{"amount":"+0.8325751423835754","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":"Q5951962$3DE50C2C-A493-4E07-B3B9-1A7A6990CCBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9917f88bffa1c6348674bc8796b7f24b00048733","datavalue":{"value":{"entity-type":"item","numeric-id":4645927,"id":"Q4645927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"870212f60aa0eb5ab93a4eac9220b6e31f28167b","datavalue":{"value":{"amount":"+0.8316696882247925","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":"Q5951962$0A435AAC-9378-4F0F-811C-18B27F06A63F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b05fccccfd9398c598074e1f15dae80465c5439","datavalue":{"value":{"entity-type":"item","numeric-id":1016120,"id":"Q1016120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"172702694e92810191d330098a6dfbe69002e2fe","datavalue":{"value":{"amount":"+0.8302978277206421","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":"Q5951962$7608141A-26EC-4029-9CE3-A5ACEFCC780C","rank":"normal"},{"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":"af7ab13f39dcee638210bab0a5fa444c5401b7e4","datavalue":{"value":{"amount":"+0.8276723623275757","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":"Q5951962$C7FBE250-4850-4937-A7A9-E51B12D3B17F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5951962","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5951962"}}}}}