{"entities":{"Q2046266":{"pageid":2057008,"ns":120,"title":"Item:Q2046266","lastrevid":78409301,"modified":"2026-05-06T11:31:31Z","type":"item","id":"Q2046266","labels":{"en":{"language":"en","value":"Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7382627"}},"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":"Q2046266$F3276087-D39B-4953-B8EF-AB17761D866C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"95354591654601efb1869757cdd4d933271fcc92","datavalue":{"value":{"text":"Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2046266$6AB4FF52-6112-411A-B93A-D05DB94F7F15","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3e2950e841e71db17667a34cdaa3e0f7fa278bc2","datavalue":{"value":"1479.90182","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2046266$982B5776-60E5-4B5D-814A-BBEFB8CCCAB3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5402eb9c10c6296e25791c8b08115e53c8bf4b4e","datavalue":{"value":{"entity-type":"item","numeric-id":296295,"id":"Q296295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2046266$6835C421-AC0E-4AC1-8563-6E007BC5FB20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5cbbab7857ed063411ee2e0f27c5a6003d347a34","datavalue":{"value":{"entity-type":"item","numeric-id":1702829,"id":"Q1702829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2046266$5329F099-FE37-4759-94AC-7FD087C2FFB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d3db05661f4038fd71c861561cbafad4cd248f4e","datavalue":{"value":{"entity-type":"item","numeric-id":591600,"id":"Q591600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2046266$31B7410D-9B07-4728-BE80-F9975167BE27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0a7a238e7c3c3c15efac441de9739aafc131e5f","datavalue":{"value":{"entity-type":"item","numeric-id":1690579,"id":"Q1690579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2046266$67697C83-C603-43BE-ADD7-C148AED7D17E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8c9a1d032b4dee05705e8b2f4f60118816c12892","datavalue":{"value":{"entity-type":"item","numeric-id":116038,"id":"Q116038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2046266$70EBACF1-F57A-4A0A-9C53-BAC66C355CDC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7e9d8f11f2475597204ac70874001750a176c698","datavalue":{"value":{"time":"+2021-08-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2046266$8FEC6EA2-2BED-49A2-95BC-60F078EB0F85","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5f1f7abb01dda862e394e90ad67eefaec6cd57df","datavalue":{"value":"The authors propose a threshold greedy algorithm for the problem of maximizing the sum of a monotone non-negative diminishing return submodular function and a monotone non-negative supermodular function on the integer lattice with a cardinality constraint. The relation between the value of the solution returned by the proposed algorithm and the optimal solution value is estimated by a constant. With this purpose the authors introduce a concept of the total curvature on the integer lattice for a monotone non-decreasing non-negative submodular function and for a monotone non-negative supermodular function. They also formulate a linear program whose objective function approximates the estimated relation.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2046266$314D8B26-D2CB-43E4-BFAF-AA6E51966FCE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"937feade3061e9f7774221fad1a9d078a901d790","datavalue":{"value":{"entity-type":"item","numeric-id":336765,"id":"Q336765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2046266$0F49CD9E-CD9C-4AFD-B3E8-01E4586C1DAA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2046266$493C7816-ACDD-4015-A4AB-317057351182","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2046266$D43A0436-07DB-4C0E-BF44-6E4E6C0AEA3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2046266$BB9EA03D-CC87-4357-B8C9-196E769A8A40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ccd1dd4cefa81e8158b9f080486a4eaed61a9ee8","datavalue":{"value":"90C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2046266$42371E49-9639-4E15-A70F-5BCD063E2F61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2046266$CA5B7360-E8A0-49AE-84C0-0712F61D4147","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2046266$6FF2EFA6-38D7-4875-97D4-7AD90F765413","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9cfd70dd01c45c26bf7c2cc9bbb633dfa9a92573","datavalue":{"value":"7382627","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2046266$9B7E287C-0FF6-4B50-9741-D295CC05C865","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ce6d3e05c67e7e482c47120f2d05461bf865564","datavalue":{"value":"submodular function","type":"string"},"datatype":"string"},"type":"statement","id":"Q2046266$ABDDAB4C-A008-40DC-8809-CB00CC6BBF6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"720516741c3f907fac3a048b220a5821f69c11f2","datavalue":{"value":"supermodular function","type":"string"},"datatype":"string"},"type":"statement","id":"Q2046266$3AE49D0A-4E80-4598-A007-866059A44BDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c3c0ec917e838f1dacb38d5bf4b9fb5f5a972c0e","datavalue":{"value":"integer lattice","type":"string"},"datatype":"string"},"type":"statement","id":"Q2046266$5E9C61DF-A4FA-4AF9-B7BE-1398F302B07A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb9ea69f98993ec8c397b4afcc0cf69fb524db51","datavalue":{"value":"cardinality constraint","type":"string"},"datatype":"string"},"type":"statement","id":"Q2046266$010534BF-DFB4-42D6-ABA7-A339AE4939FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"705f1dc89bae029b773a3536082b5ad0c15c445d","datavalue":{"value":"threshold greedy algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2046266$6AC58B72-01B1-4BCF-BBD3-DD59CC383C09","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":"Q2046266$A1A0C65D-0F84-4E86-B75A-E235C756B267","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cac936d5cad3d852efd310fefbae154d9587c671","datavalue":{"value":"https://doi.org/10.1007/s10898-021-01014-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q2046266$F90F509D-E71F-4A41-A5CD-3A0247F6091D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0e325f5b7f7a83cf7ceb6c03e7fcd6adc1721fe3","datavalue":{"value":"W3142764332","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2046266$04F0B7DB-3A0A-40EA-93F7-0D4E22D86544","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5271a3b3a8531aa6b265a811094697ebb1bab23f","datavalue":{"value":{"entity-type":"item","numeric-id":3225171,"id":"Q3225171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2046266$A4935A68-CA52-45F5-A7CE-2F4399356655","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ca830b887d4626a81e35fdb0cace7c0ec57e0b8","datavalue":{"value":{"entity-type":"item","numeric-id":790044,"id":"Q790044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2046266$DFCD7272-03FD-47BD-A2D6-08792E13D43E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77c3a1730a9a48ab34ee8089cb351bc4c6321d3e","datavalue":{"value":{"entity-type":"item","numeric-id":1027590,"id":"Q1027590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2046266$E427B73C-F57F-4FBB-A9A1-7BBE8E2B6EF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be5f1aa9294846cde8376d837af26608b9f41054","datavalue":{"value":{"entity-type":"item","numeric-id":2941641,"id":"Q2941641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2046266$CD02E0D3-C78B-46F7-BB09-E6F539E60B36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e6f2521f9ee7a0316d4b7815bef4b51c61a20c6","datavalue":{"value":{"entity-type":"item","numeric-id":3096108,"id":"Q3096108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2046266$F518A097-14C9-4542-9996-552C3DECB376","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebd4bd40c69ed0b570684e26eee138b54f29c21a","datavalue":{"value":{"entity-type":"item","numeric-id":4178796,"id":"Q4178796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2046266$70E5F07A-6034-4873-B120-8DCFCF6D1ABD","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":"Q2046266$92B4CAE2-B50D-409A-BDCD-994A5E412082","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"521236195e8c1b65dfc0d8a560fecc45a7c4539e","datavalue":{"value":{"entity-type":"item","numeric-id":1433658,"id":"Q1433658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2046266$592300DB-655A-4F99-ADED-27EE02464355","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"331ac594915d739c9c3b58c689ff3cd810b28e71","datavalue":{"value":{"entity-type":"item","numeric-id":3549686,"id":"Q3549686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2046266$77763028-5DC4-48AA-BE3E-5779A05965DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36f272bb27ef5224ac6f7695c0bb0247ad88c2b8","datavalue":{"value":{"entity-type":"item","numeric-id":5232162,"id":"Q5232162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2046266$238EAA8C-FFFC-4327-9175-070EC8AB3463","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"67da9bffb31451f6d67a477250dd3167aadd1a29","datavalue":{"value":"10.1007/S10898-021-01014-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2046266$D669E7C4-8808-4E93-9565-A5756CB6784B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5abef1618c549a965dec1856bb39cbe951af0c4f","datavalue":{"value":{"entity-type":"item","numeric-id":5216445,"id":"Q5216445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1468df8c6ed7607abf4c3928525614dab12d5cb","datavalue":{"value":{"amount":"+0.8514731526374817","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":"Q2046266$D6C151C8-EE99-46A5-8B2A-E27428872649","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3de0b701df7fb4e9fd50b401bcf8ca1e923a3bd","datavalue":{"value":{"entity-type":"item","numeric-id":5207510,"id":"Q5207510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0b363f12696e15a5d31d3c7b56b5a46b2a16590","datavalue":{"value":{"amount":"+0.8493807911872864","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":"Q2046266$ECA6AE88-ACBD-4AD9-A13F-3E8C28ACDAB5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Maximizing_DR-submodular%2Bsupermodular_functions_on_the_integer_lattice_subject_to_a_cardinality_constraint"}}}}}