{"entities":{"Q583110":{"pageid":584877,"ns":120,"title":"Item:Q583110","lastrevid":62939835,"modified":"2026-04-11T09:06:50Z","type":"item","id":"Q583110","labels":{"en":{"language":"en","value":"On an optimization problem with nested constraints"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4131956"}},"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":"Q583110$389D6A63-3326-4806-8DDA-B285B4DF110E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2ce11729c73989765b21adddc940b6dddb1924b2","datavalue":{"value":{"text":"On an optimization problem with nested constraints","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q583110$435111D4-A42A-453E-90C4-EF9D9884C338","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d95b59def2ea6fbd09a8f2086066a2431baf9ecb","datavalue":{"value":"0691.90063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q583110$0F378D9A-711C-4005-BB45-0F26054C162F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5e496da490c53ce3b03323ae0ee18c7b1e84f5db","datavalue":{"value":"10.1016/0166-218X(90)90098-W","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q583110$48FC3EF9-ADC0-4EEA-A8E9-024897BAFFAB","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":"Q583110$EB761155-861F-487E-A49A-CDEB1FCAF6F7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q583110$B22E6CBF-C0FB-48C4-A5FB-68888F1EB74B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"eed4ff0c1218ba3ea01c83da02130c408ae657ec","datavalue":{"value":"The problem considered is: maximize \\(\\sum^{n}_{j=1}f_ j(x_ j)\\) subject to \\(\\sum_{j\\in S_ i}x_ i\\leq b_ i\\), \\(i=1,...,m\\), \\(x_ j\\geq 0\\) integer. The constraints are assumed to be nested, i.e. with respect to inclusion the graph with vertices \\(S_ i\\) is a tree. Two algorithms are presented, resp. for the case that each \\(f_ j(x_ j)\\) is concave, with running time \\(O(n \\log^ 2n \\log \\bar b),\\) and the case that all \\(f_ j\\) are equal, with running time \\(O(n+m\\log m)\\). Here \\(\\bar b\\) is less than the largest b.","type":"string"},"datatype":"string"},"type":"statement","id":"Q583110$E0555963-1B59-4706-A429-A249513FA9C7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q583110$D9C912C8-423D-49A0-A862-E9EBAEB9F3C5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"312ab75982137caeaac957b82996e11530cebe76","datavalue":{"value":"4131956","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q583110$587A0CFE-EEEA-469B-B096-A3A6C533CA8C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8f16e34283cc5dcc42dc3180c867c78d75c594b","datavalue":{"value":"nested constraints","type":"string"},"datatype":"string"},"type":"statement","id":"Q583110$FEB543E4-B77D-479B-8886-812FBBF12D53","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"db0bc6add0ebedcaa061a5710e3a7f9facbae65a","datavalue":{"value":"Q56324124","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q583110$6C96A060-FAA8-45C5-BA76-D1DD491E6256","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0ac6079b2082bbed271309fb2d51b5b4c5dd28d8","datavalue":{"value":{"entity-type":"item","numeric-id":247119,"id":"Q247119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q583110$BF723F4E-CB6C-477D-89FC-25AFEF8C292C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ee31696a3be6df3bdd79f474603a4526c11abc4","datavalue":{"value":{"entity-type":"item","numeric-id":1577015,"id":"Q1577015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q583110$B44F4265-3EB4-42DF-96A2-3A6C36FBF26F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"773ccef7b8ad8b5275f8369121560572282db928","datavalue":{"value":{"entity-type":"item","numeric-id":976026,"id":"Q976026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q583110$809CFA60-3141-4D72-B938-B109313B091A","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":"Q583110$BA53E28E-99E2-4F75-9B48-D605F7EB786B","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":"Q583110$948FD3BF-A6AE-4D83-A02C-6E661026CC48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96117a52c20050e4fa756827b6c5a9691276c6e3","datavalue":{"value":{"entity-type":"item","numeric-id":3315472,"id":"Q3315472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q583110$2CA52C38-D6FA-42F4-88AF-CB871217C04D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bc2e0d2db0a6d299eb21235fc0a97593259b0d3","datavalue":{"value":{"entity-type":"item","numeric-id":1394121,"id":"Q1394121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q583110$44EE0E7D-9D1F-408E-B311-C4EA29CCFE1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7aae35d25f4436919abce0bbbbcb749b0fad7196","datavalue":{"value":{"entity-type":"item","numeric-id":3318501,"id":"Q3318501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q583110$5978671A-BC00-460F-8068-DADE9A90CD5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"688b3c56dc876556e56635537e5f6821ffe217e5","datavalue":{"value":{"entity-type":"item","numeric-id":579126,"id":"Q579126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q583110$2BE3C51F-FF39-4572-AFD7-9776C126EF48","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":"Q583110$2249AF57-11E0-4FB2-819E-49A7970300F0","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":"Q583110$0262FD31-AA47-4C1B-ABED-EF0B6BFF8DE1","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":"Q583110$63389CBD-4F45-4D08-A07D-33A00FD24EAF","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":"Q583110$499C2B29-CA43-4DC2-A3BF-21EE951BEDD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8635a293f0260693024421bcdf9d97cffc1890ad","datavalue":{"value":{"entity-type":"item","numeric-id":4010349,"id":"Q4010349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q583110$9CFE4C36-4577-4B08-9DDC-0D76A988A9C3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"acd4c3a217ae6a1db3ad8e84fe264bb78e572192","datavalue":{"value":{"entity-type":"item","numeric-id":3318501,"id":"Q3318501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7097b4cf255814b415aa5109bc51e74cc8c99d45","datavalue":{"value":{"amount":"+0.8419673442840576","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":"Q583110$93CBD1A0-2BE9-469A-9BD7-2EE09DC678BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1369c1479d1a876fde6c11d919d50489664ac55","datavalue":{"value":{"entity-type":"item","numeric-id":3427663,"id":"Q3427663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88fdc14043c0a9a3aea5bfcff20c4d8c53bc9b70","datavalue":{"value":{"amount":"+0.7777495980262756","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":"Q583110$C31755E7-16A9-4067-900E-FE36596C0BD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"470c319ae8438298b9d733352f80c0df867997a8","datavalue":{"value":{"entity-type":"item","numeric-id":3841521,"id":"Q3841521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"34e72a69bfe88503c6d3257271c4601b184b998e","datavalue":{"value":{"amount":"+0.7722198367118835","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":"Q583110$8966180E-2D32-4251-8DC4-EACCA24E30DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4eaa1e0e3436df6bba6b993b0fc8b27de0fa8a36","datavalue":{"value":{"entity-type":"item","numeric-id":579126,"id":"Q579126"},"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":"Q583110$5A1C3F9C-AD16-4A51-8E42-483701FC85E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d6004a632fb246fd8e4b73c558c284d4099569b","datavalue":{"value":{"entity-type":"item","numeric-id":3682237,"id":"Q3682237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90b682ff08c673cbb70a4dc9df412a020958cb0a","datavalue":{"value":{"amount":"+0.7463254928588867","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":"Q583110$73F03BAF-5110-4D3C-AFDB-DF80E578F418","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On an optimization problem with nested constraints","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_an_optimization_problem_with_nested_constraints"}}}}}