{"entities":{"Q1803670":{"pageid":1814412,"ns":120,"title":"Item:Q1803670","lastrevid":72699927,"modified":"2026-04-14T06:37:14Z","type":"item","id":"Q1803670","labels":{"en":{"language":"en","value":"Note on combinatorial optimization with max-linear objective functions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 221650"}},"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":"Q1803670$50A14192-B884-4F4B-9C2B-0964677BB68D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4f2d648dd9e4946bc3b5bd794250eb469b67a8b0","datavalue":{"value":{"text":"Note on combinatorial optimization with max-linear objective functions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1803670$349FDC7C-1CD1-4D7E-851C-E75874AB1BBA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8e9e501b06f34e983adf4a4c8125346e2665a2b9","datavalue":{"value":"0777.90046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1803670$9DE05082-5E2C-4014-A1BD-39BDB237C99C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c0fae75605f3ca6b5e6247f62a2b27c84488d35f","datavalue":{"value":"10.1016/0166-218X(93)90043-N","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1803670$AD25DFE9-306B-4AEE-A72C-4F57E511F1E3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"940f3fb869ef57998d146c6cd97bee2b0b17af49","datavalue":{"value":{"entity-type":"item","numeric-id":852962,"id":"Q852962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803670$0F47370D-AF9B-4BA4-8240-AF038B256696","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e50be6e020f540bbd257789357e2fcbd9ed3a74e","datavalue":{"value":{"entity-type":"item","numeric-id":166234,"id":"Q166234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803670$C3E32823-9881-49B2-96C3-125885B42A80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9ca552b5a09a951163fe2671a2056a7d7d226e25","datavalue":{"value":{"entity-type":"item","numeric-id":496638,"id":"Q496638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803670$0653B822-D7EE-44E5-8932-F9526BDB19AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"494ec1e1ae3705dab70ace1ce6bbd479ce55d0e8","datavalue":{"value":{"entity-type":"item","numeric-id":505110,"id":"Q505110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803670$CBD5E82B-BD5C-47C6-8375-ED063578B9BB","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":"Q1803670$5DE029B1-DD63-4C3B-BBC5-DA3184A94387","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be4381b75afe2df0dbe37cd1a66e006418c0c5aa","datavalue":{"value":{"time":"+1993-06-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1803670$245D8225-4152-478C-A814-68C204DA658C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"abc7c16a570ca23d46778c2ec74095dfddfc95fa","datavalue":{"value":"The authors consider the problem (MLCO) of minimizing \\(f(x)=\\max\\{c^ 1x,\\dots,c^ p x: x\\in S\\}\\), where \\(c^ q\\) for \\(q=1,\\dots,p\\) is a given row vector in \\(\\mathbb{R}^ n\\) and \\(S\\subseteq\\{0,1\\}^ n\\). They suppose the set \\(S\\) always has a special structure so that a single linear objective function can be optimized over it in polynomial time. In the paper it is proved that MLCO is NP-hard even for the simplest case of \\(S=\\{0,1\\}^ n\\) and \\(p=2\\), and strongly NP-hard for general \\(p\\). The relation of MLCO problem to multicriteria optimization (MCO) problems is presented by the following theorem: ``For any instance of MLCO problem there is an optimum solution which is efficient with respect to the cost function of MCO problem''. In the last section of the paper some lower bounds for the branch-and-bound method are presented. Overall, the paper is written in a clear style and is easily readable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1803670$60B158A3-1F18-4A29-9FE3-B6612B7FEB73","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1803670$E4719749-C33D-495B-94DC-2C695B3EA879","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1803670$FA2C8447-15C1-481C-90F9-424ED36D9E18","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c4a08f9a9c1e42f3010d9e80d45a790b23319d4d","datavalue":{"value":"221650","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1803670$7FABF24A-A756-46C5-868E-7876C35EA5A8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c0f546e75fbf00bb253580c1a0c12b50a0e4ca93","datavalue":{"value":"max-linear combinatorial problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1803670$119794E9-BA85-4505-9CD7-28235A681E9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdf4ca3d9fb773e560a856fad1c1f12857df3e40","datavalue":{"value":"strongly NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q1803670$917FBDC3-B0DA-4E61-B77F-B1F382D33B52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f560d2e67395a528af143d4c3846c29db472a4c","datavalue":{"value":"multicriteria optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1803670$22F33F4E-F6E6-4091-A705-6A5E41A3954B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q1803670$63D75A9D-3706-40F0-BC48-C38CB4368EE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"32b70193b15cfa9820eaa83513ddb2267d9b694a","datavalue":{"value":"branch-and-bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1803670$55449C07-AB60-411B-930E-D4DE3E9E4B43","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2b972ef175b4299fdbfc53bb71881ff0c6d5f85c","datavalue":{"value":{"entity-type":"item","numeric-id":587047,"id":"Q587047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803670$BCE7EA6E-7BCA-4E41-B9E9-13D5D05F6B19","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":"Q1803670$37B3EA52-0082-422D-AF35-10E092E1710B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e3e2312b1eb568d0fcbb0a84ca405d008834f6a","datavalue":{"value":{"entity-type":"item","numeric-id":1824560,"id":"Q1824560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803670$A480C0D7-FEC6-4399-A93C-F253F5446B72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73fd3dc583a90b41142d22a75f9670b8b8112da1","datavalue":{"value":{"entity-type":"item","numeric-id":797497,"id":"Q797497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803670$136B306C-05C6-4DFB-B121-FF3D3E4A844F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"faec2b458737c1252de3c75b688664fde0055455","datavalue":{"value":{"entity-type":"item","numeric-id":3712126,"id":"Q3712126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803670$B8FC6968-CCE8-4875-BEAD-EDD2557BDF9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94abc8705ebb37f31d87bcf9eca153668a350887","datavalue":{"value":{"entity-type":"item","numeric-id":4226179,"id":"Q4226179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803670$BCEBE6B8-661D-4214-82D4-BD6EF99B4002","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":"Q1803670$B94E5D74-B6ED-486D-8203-D58CD654C75C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de7ecd50592d3eceffc4b45a335c3d77ba4be55f","datavalue":{"value":{"entity-type":"item","numeric-id":3342227,"id":"Q3342227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803670$9B970B1B-477C-46B6-8521-A94DD34659DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f034a02d229a745fe31c0f5a73440c6132e42cc","datavalue":{"value":{"entity-type":"item","numeric-id":3823390,"id":"Q3823390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803670$84FC5726-8C01-490C-BAF6-8C8C423F39C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e008f38bb6e3520a5336a8cd2a0e4568af5b76ef","datavalue":{"value":{"entity-type":"item","numeric-id":2553907,"id":"Q2553907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803670$A04156C8-4539-45DE-B5AB-C845C64DBF34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1dbbe3ac3158330a6990b58a9a558d77085ad86b","datavalue":{"value":{"entity-type":"item","numeric-id":4039868,"id":"Q4039868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803670$6ECD8921-C0EC-470E-A30D-0A39F9A64824","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08681459d59a4941619e8e81c7e6055c81f4896d","datavalue":{"value":{"entity-type":"item","numeric-id":3778558,"id":"Q3778558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803670$FB24DA7F-850D-4F6B-B979-41D833A92C2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4def438d8a28321802a44dbba53d7d9b373961a","datavalue":{"value":{"entity-type":"item","numeric-id":3923934,"id":"Q3923934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803670$E7DFD244-90A0-4BE4-A459-BBA2992AE52A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bbf51dc0fc76dbd439d6347874a2d8d27d946bd","datavalue":{"value":{"entity-type":"item","numeric-id":3968756,"id":"Q3968756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803670$6DCB875A-07CE-4877-A40D-FAD871296C84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0122bc6c261148a34706fd8a0b6a8de73ca9411c","datavalue":{"value":{"entity-type":"item","numeric-id":3703589,"id":"Q3703589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803670$6F5BF10E-6FDF-4793-A085-1CFF36C82DE3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9c579aa62459d9de004ab738945403dd18d5837e","datavalue":{"value":"https://doi.org/10.1016/0166-218x(93)90043-n","type":"string"},"datatype":"url"},"type":"statement","id":"Q1803670$5DC2CD67-CBF4-4D6A-8D9D-54AB5832D1EF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c1e154de8757504ea051f293b7bae1ad5fba1301","datavalue":{"value":"W2098120964","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1803670$B221E469-03B3-48BE-8450-BB79A76A951C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d60f9a87da37899a0a5533a7b8c8265c8cf654f","datavalue":{"value":{"entity-type":"item","numeric-id":3983485,"id":"Q3983485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c92d1d15986e5b68675b2c29bb8c4d5ece09b966","datavalue":{"value":{"amount":"+0.7627342343330383","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":"Q1803670$683C2FA2-D5A7-4455-8DCA-C8D50547F33D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"87a138a5c74c22b23747c161a311533f91e8d246","datavalue":{"value":{"entity-type":"item","numeric-id":1824562,"id":"Q1824562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3d39e4e9475b0112a8167db7e00642c3773544a","datavalue":{"value":{"amount":"+0.7618827819824219","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":"Q1803670$FEC6D09D-945E-4013-B996-1A25E36C6208","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab99c7c73f491145c7ae590b3aef5a2728661ba0","datavalue":{"value":{"entity-type":"item","numeric-id":4514764,"id":"Q4514764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0cc621f72576984f096d007b50bc3a64629f6d6","datavalue":{"value":{"amount":"+0.7468481659889221","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":"Q1803670$AC494E1B-0A19-4D4F-8F13-FEB80CBBE781","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbcd620a974b9de969900168fe5f87f8a3b7c3c0","datavalue":{"value":{"entity-type":"item","numeric-id":4670576,"id":"Q4670576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"242ca57a1c737bbbead5692d62fd8275e3dc4299","datavalue":{"value":{"amount":"+0.7454862594604492","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":"Q1803670$17BDD817-62CA-4EEB-B3E9-1D4CCE97CB0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3eb7ae59bbf8810cb81bc4fdda53be649b3fc70","datavalue":{"value":{"entity-type":"item","numeric-id":4896386,"id":"Q4896386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8577548267bee0b63e22731d41eb1e9c95e79b61","datavalue":{"value":{"amount":"+0.7452786564826965","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":"Q1803670$A21A62A5-A3A0-4AF7-911B-5358E8836C15","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Note on combinatorial optimization with max-linear objective functions","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Note_on_combinatorial_optimization_with_max-linear_objective_functions"}}}}}