{"entities":{"Q579126":{"pageid":580893,"ns":120,"title":"Item:Q579126","lastrevid":62977350,"modified":"2026-04-11T09:25:50Z","type":"item","id":"Q579126","labels":{"en":{"language":"en","value":"An algorithm for a separable integer programming problem with cumulatively bounded variables"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4014452"}},"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":"Q579126$C14EAE27-C678-4E15-AFBB-1726897429E5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3d572381d84a543b1b6841a5f615b059064c37d9","datavalue":{"value":{"text":"An algorithm for a separable integer programming problem with cumulatively bounded variables","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q579126$FF081E4E-C41D-443E-B715-D54B39BD490C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ea836d36a91278c03c9d2cde60f56ab31c4cf49d","datavalue":{"value":"0624.90071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579126$81A456E0-4037-438B-A983-8A7DB735F21F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0f60b2ab202622fbd7c256436b5a10006fbdb650","datavalue":{"value":"10.1016/0166-218X(87)90070-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579126$D399E250-300B-4396-BAE0-A43A57BE0B17","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9153f57b49379c8f42a6fee983336120467fb8fa","datavalue":{"value":{"entity-type":"item","numeric-id":551798,"id":"Q551798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579126$9BAEFD47-8C66-44AF-90C1-9C83A82B61C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f3994b3ea7b242f980d845d7f38f3a45e589bc28","datavalue":{"value":{"entity-type":"item","numeric-id":592710,"id":"Q592710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579126$1F7A0E88-92AB-4DC1-99A1-7A5CA63A6E86","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":"Q579126$9E07CC51-2BDD-4BE5-87F5-7CCDC3AD9225","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q579126$29161C20-9D1D-4F1B-A702-CEE1C9606157","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"52d51ac40d5c829031f4c4d7784a9d7e70b131de","datavalue":{"value":"The authors analyze the problem  \\[ P_{(p,s)}: \\max \\sum^{s}_{i=p}f_ i(x_ i)\\quad s.t.\\quad \\sum^{j}_{i=p}x_ i\\leq b_ j\\quad (j=p,...,s) \\]  with  \\[  x_ i\\in X_ i:=\\{0,1,2,...,b_ i\\},\\quad f_ i\\text{ non-decreasing and concave on \\(X_ i,\\) and \\(0\\leq b_ p\\leq...\\leq b_ j\\) with }b_ s\\geq s.  \\]  First a sufficient condition under which an optimal solution to a Lagrangian relaxation also yields an optimal solution to \\(P_{(1,m)}\\) is developed.    Secondly an incremental (but pseudo-polynomial) algorithm (``greedy'') is given which constructs the lexicographically largest optimal solution to \\(P_{(p,s)}\\) in \\(O(m\\cdot b_ m)\\) time, where \\(b_ m\\) is an upper bound on the sum of all variables.    By recursively solving \\(P(1,\\lfloor m/2\\rfloor)\\), using the monotonicity of the lexicographically largest optimal solution (in s) and a divide- and-conquer approach the authors get a recurrence relation for this refined algorithm (``quicker greedy'') which solves P(1,m) in O(m log(m)\\(\\cdot \\log^ 2(b_ m/m))\\) time - where each function evaluation \\(f_ i(x_ i)\\) counts by one.    In the special case where \\(f_ j=f\\) \\((j=1,...,m)\\) the sufficient condition can be strengthened and this allows an O(m) time algorithm - where additionally the floor function evaluations \\(\\lceil y_ j\\rceil\\) resp. \\(\\lfloor y_ j\\rfloor\\) count by one, too.","type":"string"},"datatype":"string"},"type":"statement","id":"Q579126$36B3F7AF-9D2B-4AA6-B2C7-59C6BF6DE256","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579126$C5A1D065-7E62-4C41-9870-E361A54F2F08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579126$023450C0-B9C9-4FB4-BE3C-B270C8ECA24F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f6e5f24144b3e9472df59069e61e4af2551f07de","datavalue":{"value":"4014452","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579126$4CC5B9A3-C9B4-4AFD-AA0E-4D72E67F93BF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0c4caeb46bd9ef797fa7cd1b6fc32ee34dcd1d55","datavalue":{"value":"separable concave","type":"string"},"datatype":"string"},"type":"statement","id":"Q579126$F54AD4AC-8D57-46A4-91B4-14B0532BC57E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bc23bff4123783798c8ea22b4f07b1a406cbad03","datavalue":{"value":"objective function","type":"string"},"datatype":"string"},"type":"statement","id":"Q579126$3E36A260-2692-4F0B-BB39-C5F71254CB92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a59e0c1eb51c50ee8b2be5656da8a2be878f5f1","datavalue":{"value":"Lagrangian relaxation","type":"string"},"datatype":"string"},"type":"statement","id":"Q579126$E52D4D44-F70C-46E6-A696-125DFEC80B59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"222c6ea3b465d08cf71dfc59e7375cfc1f99eece","datavalue":{"value":"lexicographically largest optimal solution","type":"string"},"datatype":"string"},"type":"statement","id":"Q579126$EDCC47D4-A132-45CA-8871-6EAFD67D1FFD","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"d2c173788cec6ba4d69efbe4fb2b251d1a357341","datavalue":{"value":"Q56324145","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579126$02F023CE-DA53-449F-A9BE-E82C436AEBFF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"111aa4d205b7adb5a8dca99e52744f61a537d2b5","datavalue":{"value":{"entity-type":"item","numeric-id":647398,"id":"Q647398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579126$F9B1E2E7-8B9C-498D-8EDF-0189DE6399D8","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":"Q579126$DC9EB497-8A9E-4891-83C3-FBC0A8ABC071","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7af92e1b72183a3caeef57d9cd4d4a7a32fad3cd","datavalue":{"value":{"entity-type":"item","numeric-id":3956742,"id":"Q3956742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579126$7AA7B5DC-E719-426A-918C-F4317524D3E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a92fa58347df66baf224b4b980402e96c769aa88","datavalue":{"value":{"entity-type":"item","numeric-id":3040940,"id":"Q3040940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579126$07E56101-DAC3-4EC7-AD2D-3E8AF320794F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"083d97e730faf90a4132402a3f045bdbf076bc3c","datavalue":{"value":{"entity-type":"item","numeric-id":3919449,"id":"Q3919449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579126$7C9AF0B8-AFC7-401D-A929-051922A32045","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cdb822f0d9f96310737f9e1aa9ae348ece881b72","datavalue":{"value":{"entity-type":"item","numeric-id":1161291,"id":"Q1161291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579126$D6550A9F-0E80-4567-8E20-435CE46EB15C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"332b6569eae4645fb444023e8b44b3148f60612c","datavalue":{"value":{"entity-type":"item","numeric-id":4190436,"id":"Q4190436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579126$7721E5AD-4B1C-4681-ACCA-3075A2C80B2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"13ea28780a2ceb401aa50ede4fa3391a063eab5e","datavalue":{"value":{"entity-type":"item","numeric-id":1152307,"id":"Q1152307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579126$378B6FBC-F5EF-486C-B8D1-2130DBB52425","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9199ceeaa47e41e133429a47068afe4eba48a41e","datavalue":{"value":{"entity-type":"item","numeric-id":3873922,"id":"Q3873922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579126$DFFECCFD-F5A2-4BAE-95D4-84225B5AC305","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5bb9c8f7cf967bfca82072cc0dff6892282f7e24","datavalue":{"value":{"entity-type":"item","numeric-id":1417561,"id":"Q1417561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12051f20ad9bebc9ed27c0162067baa953eeb651","datavalue":{"value":{"amount":"+0.7696332335472107","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":"Q579126$9FEC202C-AFEF-4CBC-AF94-68BEF6F83A92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7758bff634080bba5c7dc8c60384f5419d44d7dc","datavalue":{"value":{"entity-type":"item","numeric-id":2713931,"id":"Q2713931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b8bfa353d89cac2e3fc8118d726bf87477fb170","datavalue":{"value":{"amount":"+0.7693549394607544","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":"Q579126$44D12792-A30D-4CDB-A67B-F5E291BB19F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dba3f661f5b140cee5ef087c71a639cbecff6c1f","datavalue":{"value":{"entity-type":"item","numeric-id":3773696,"id":"Q3773696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90b411be4c88021f6aad927d5135fd03c7916ebf","datavalue":{"value":{"amount":"+0.7691820859909058","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":"Q579126$E603652E-DFE0-444F-8965-094BBF6DAA15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51e124b1d621cf23e7410f6bf02a1c3469afb1a0","datavalue":{"value":{"entity-type":"item","numeric-id":583110,"id":"Q583110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5e06ebf1b63467c1890c36dc044731c68cb0649","datavalue":{"value":{"amount":"+0.7675550580024719","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":"Q579126$485380B6-C42A-48A1-B369-4BAC221FF6AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7d7e8bfa1898c8964d118a6c09cf72b46c4a9e5","datavalue":{"value":{"entity-type":"item","numeric-id":5202524,"id":"Q5202524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0f684614c75f755a8278b8645f4c8df3e15cc78","datavalue":{"value":{"amount":"+0.7618488073348999","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":"Q579126$204F017D-25F6-4A99-B888-88C24AE8E6F3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An algorithm for a separable integer programming problem with cumulatively bounded variables","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_algorithm_for_a_separable_integer_programming_problem_with_cumulatively_bounded_variables"}}}}}