{"entities":{"Q1069444":{"pageid":1080196,"ns":120,"title":"Item:Q1069444","lastrevid":55946578,"modified":"2026-02-21T10:02:23Z","type":"item","id":"Q1069444","labels":{"en":{"language":"en","value":"Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3934772"}},"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":"Q1069444$C28BD8FB-320D-4F5C-BA0E-DE9A76998A08","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e336b06ce863df0984e218bdfd147f108abc57d0","datavalue":{"value":{"text":"Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1069444$70FF2995-4FD1-42DA-9A1A-362EA5E03FAD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b71627020f1b97bce826cfe998b632ddb5e6b910","datavalue":{"value":"0583.90067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069444$0162E092-95A4-4664-9E51-59E5B8533790","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"871a57728604b2509c4dd419b7fcce157401f2d6","datavalue":{"value":"10.1016/0166-218X(85)90035-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069444$17AA1910-7CBC-4FC8-92E0-9E8F21CE9A6E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8b2480f70a96a0e09506405db969492fd41acf1c","datavalue":{"value":{"entity-type":"item","numeric-id":325411,"id":"Q325411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069444$3E2620CB-0744-4F16-AEF0-0C369EE48D70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1f1c6a8167c7f3e97dc242c6c4f58c64741e146","datavalue":{"value":{"entity-type":"item","numeric-id":176416,"id":"Q176416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069444$118C18C5-E065-4CA8-91F4-454C95ADF439","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":"Q1069444$557D5F29-95D9-4F17-BAAF-BAC8B8796517","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1069444$38311F6B-D382-458B-959F-F170B84AE23C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6922b22e65f42a94c83473a9efd0904dc9d363c0","datavalue":{"value":"The problem of maximizing a pseudoboolean function (or equivalently a set function) which is supermodular, has many interesting applications e.g. in combinatorial optimization, operations research etc. Up to now, a number of special cases of pseudoboolean functions have been known, the maximization of which can be converted into the search for a maximum flow in an associated network. These were essentially the so-called negative- positive pseudoboolean functions (which, as will be noted here, turn out to be supermodular). First it is shown here how these results on negative-positive functions can be more easily derived by using the concept of conflict graph. The conflict graph approach is then generalized to extend the class of problems amenable to maximum network flow problems to the whole set of cubic supermodular pseudoboolean functions.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069444$C21F63C0-0E69-4C56-A521-17DA6A7323F0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6958ea3363ca9244e0da0201efd237a8410f9a0c","datavalue":{"value":"90C09","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069444$9E450E47-E1C7-42F4-81CC-12807AA03817","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069444$7054070C-5B74-424D-A4E6-7990C7FD5F36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069444$F0C61808-10F2-45C4-9A0F-8E5C2C4C7D05","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6af6d95e1538a3e0f66c313db8cbe57f10de280d","datavalue":{"value":"3934772","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069444$E9FEDB0A-1CC6-4ADC-A00D-8547C1C9D408","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d9889a4e3fc30671cca81fe87f3d2be322ff4e01","datavalue":{"value":"maximizing a pseudoboolean function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069444$38E64CB9-27BF-4CA6-A08B-158E58E7DF86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f20e06c4da098ad896e565332937b82da2384aff","datavalue":{"value":"supermodular","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069444$673DD5FB-579B-4F08-80DB-832DE737E014","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"327c8ceed3def07bd37ff4c6153133e64ff0aaa1","datavalue":{"value":"maximum flow","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069444$1A7DAC4F-AF20-4A55-AD06-093BE93A9CAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bda35b6cbf00134997d4c724b1f0041ecb145da1","datavalue":{"value":"negative-positive functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069444$52809712-63D1-4B42-8081-82136C93759F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5dd2d9c4e4d6c3dac4606c1f2b151c68637ccc72","datavalue":{"value":"conflict graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069444$DDC84895-8CBD-4275-B908-7EF889B8544D","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":"Q1069444$647062A9-A6C6-4467-905D-A47D0C35F7E2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5970d52508c622ebd2e26803fcea15bd8efd559f","datavalue":{"value":{"entity-type":"item","numeric-id":4117837,"id":"Q4117837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069444$1A86DDFF-FEAD-40EE-BAE3-55950CA09A8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f091a2487faa4320a607c7fc5ddd1d40ffc78957","datavalue":{"value":{"entity-type":"item","numeric-id":5615282,"id":"Q5615282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069444$10975435-3DC2-4B10-B676-E7A7D0AE86DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cfda9f5f8a6699ac53b261e43bea4e317d0b4eb","datavalue":{"value":{"entity-type":"item","numeric-id":3918060,"id":"Q3918060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069444$A0DB8E31-323B-4C67-A782-D1C8396E3AE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7a5e8aa47a9ba6bf11672824902a7b5524e1172","datavalue":{"value":{"entity-type":"item","numeric-id":3039041,"id":"Q3039041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069444$527D3704-30C8-47EE-9C50-3C6D30B1F100","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a43ca27cba6b8cbde68d00987a946f9cde333444","datavalue":{"value":{"entity-type":"item","numeric-id":3844775,"id":"Q3844775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069444$CF80D61B-6660-4864-ACA7-2825F34FD21D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c39738cea79e11456d6583aec1786d79af209b23","datavalue":{"value":{"entity-type":"item","numeric-id":5341586,"id":"Q5341586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069444$C966E28F-A131-4EA5-ACDA-0C7D99B53FB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9524d11e3548fa2018d0863de095cec92224865","datavalue":{"value":{"entity-type":"item","numeric-id":4152030,"id":"Q4152030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069444$861A4C46-56B0-412D-9118-7E8E076B32A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cb2ca458acea0e3632727170dcd237e7765fa59","datavalue":{"value":{"entity-type":"item","numeric-id":5514188,"id":"Q5514188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069444$18059C33-5F80-4234-8AF6-E8150DEB719B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069444$FF55C911-BF7C-4260-B1C8-49E4F2BD30A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"273e96f3fd191a1c748a335432845ba0076495c5","datavalue":{"value":{"entity-type":"item","numeric-id":3960718,"id":"Q3960718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069444$EDE46C16-1EF3-4CE1-A846-86ED5A0BA2DF","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":"Q1069444$78A8B707-93C4-438D-A56B-6853DD3F0464","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"849849a8734e624cdd488bd27603bced49d0bfd9","datavalue":{"value":{"entity-type":"item","numeric-id":4083698,"id":"Q4083698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069444$2D2FEFDE-7F52-4B1B-A647-809D40C4941E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf1e239dce14973bc963cb9871e26501ddc153e9","datavalue":{"value":{"entity-type":"item","numeric-id":3693267,"id":"Q3693267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069444$DC16BFD8-A6C6-47F4-8D7F-60FA3C925005","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddb2954b97127bebc5aa7915f7cbc45574575223","datavalue":{"value":{"entity-type":"item","numeric-id":4053391,"id":"Q4053391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069444$114DD52C-CB04-4097-93C8-98DED17B5CAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ddce8dfdb2c6ff15b87510943ae7a1f46327498","datavalue":{"value":{"entity-type":"item","numeric-id":4149262,"id":"Q4149262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069444$F284C30A-5DEA-4A1C-AFF2-A149EE152099","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5d2ff8ca55c71a00eb97ded234e95c181b7889c","datavalue":{"value":{"entity-type":"item","numeric-id":5603745,"id":"Q5603745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069444$9F55331B-F3C9-410C-ACA1-E4DBCEADA5E9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ca2b2e68023d103854379414726b3d16eaea85f","datavalue":{"value":{"entity-type":"item","numeric-id":2387428,"id":"Q2387428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59afe1b1409d7c87875ac6b2137f0301137f29a9","datavalue":{"value":{"amount":"+0.88999414","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069444$9BBC321B-9861-4667-93B0-728D7BA222E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34cc477da1986556852a7381ff397c33a401fe65","datavalue":{"value":{"entity-type":"item","numeric-id":3646789,"id":"Q3646789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc7e26ba4e1262aeb183db1f186e49966f800eaf","datavalue":{"value":{"amount":"+0.88334656","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069444$B26309D5-7259-4C10-B763-E194EDE98240","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a187e37fe7cf75277fef57b314e42464e250773","datavalue":{"value":{"entity-type":"item","numeric-id":2969616,"id":"Q2969616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7197b25228e011c4613e9eafcbd5e5d59104d23d","datavalue":{"value":{"amount":"+0.8705856","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069444$8F72C750-6E27-4289-BB8D-18A6A1D3A15E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a271d6c1f2947a1ce4bc3341c07ba2107d56514e","datavalue":{"value":{"entity-type":"item","numeric-id":3614209,"id":"Q3614209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"136593b0d5850579bc82caaabeb27d41b66c1cc4","datavalue":{"value":{"amount":"+0.8687358","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069444$C7A34F17-267A-4833-B208-6C6412C50862","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f905930f4601d08fa251ca75f0c222ba90a58c81","datavalue":{"value":{"entity-type":"item","numeric-id":1278287,"id":"Q1278287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"417c6a93ec213798d0e3a206d58451af6b4f8489","datavalue":{"value":{"amount":"+0.8595407","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069444$C7C761B2-0F3A-4359-99BB-CA82AFA3543E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02e2697d8dc0863bdbc810d839817249a63e51f4","datavalue":{"value":{"entity-type":"item","numeric-id":4446169,"id":"Q4446169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cae584437281237a0a13be19eceaa6ce89b434a","datavalue":{"value":{"amount":"+0.8525394","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069444$99D967E3-360B-48D7-BADE-382DF70960A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"381ca8945f4027a9de70b6cb6d4ba3877cb8d087","datavalue":{"value":{"entity-type":"item","numeric-id":5704231,"id":"Q5704231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"333d5236815e3e48b1c6f7bf7c6e76f3953db74f","datavalue":{"value":{"amount":"+0.84825313","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069444$35F80A4C-6BBF-453E-B868-21E719AA91B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22984376d6afddd53e97e2e65be31a27c5b6b125","datavalue":{"value":{"entity-type":"item","numeric-id":4962626,"id":"Q4962626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b89dd88434482c855f36f789b7bcd3c7c6bc378","datavalue":{"value":{"amount":"+0.84686494","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069444$9C0F32F3-3CA8-4488-97D7-AB22EF184FC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"248e3d80e251ebcc8b5fd759f172e4068db5f08f","datavalue":{"value":{"entity-type":"item","numeric-id":2859721,"id":"Q2859721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a8e0a68ba214aa38a42900a0ba871bea67fda7e","datavalue":{"value":{"amount":"+0.84621406","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069444$CD04A4D8-6DE2-49BC-AF0E-6A2164FB4863","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1069444","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1069444"}}}}}