{"entities":{"Q1105488":{"pageid":1116237,"ns":120,"title":"Item:Q1105488","lastrevid":49185325,"modified":"2026-01-06T17:44:17Z","type":"item","id":"Q1105488","labels":{"en":{"language":"en","value":"Optima of dual integer linear programs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4059116"}},"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":"Q1105488$47C373EB-B3FE-4D7B-814B-0FFACCBAF21D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"aa0b4c17293e874fc2e4d506df31a0b28de81dc3","datavalue":{"value":{"text":"Optima of dual integer linear programs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1105488$AB0D8FD4-9C11-4F3A-A49F-7427BC1AA067","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"68dcf777fcd59c35f5e42681554a5ca2f851c3c5","datavalue":{"value":"0648.90054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105488$F4E4E0F0-771E-4549-AC92-9D6800A5B0E8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c5aaf7416912a37709f508dbc892c246615afec6","datavalue":{"value":"10.1007/BF02122549","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105488$0B87FAD5-E97B-4BC5-A0F5-BB45EFB5D487","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f050d7429f1445acd3d9c3e3fe97add9db84e6f4","datavalue":{"value":{"entity-type":"item","numeric-id":186189,"id":"Q186189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105488$5AA5CD82-4BE6-48FC-8A3E-49382E9C2B87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c81ab3c92f44f395b025a7c9836ac25b0a0d1756","datavalue":{"value":{"entity-type":"item","numeric-id":178480,"id":"Q178480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105488$9E765B83-37C8-4010-90EE-A55024DAF2B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fb00475fd567190194461a0f087df1793eeae7c4","datavalue":{"value":{"entity-type":"item","numeric-id":6480801,"id":"Q6480801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105488$0BC77F91-C715-4896-AF3D-C0F9CECAD168","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105488$EA7FDDAD-6E66-4639-BCDB-DCB7F3240189","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1105488$A1967B9C-6096-45DF-A083-C06B4A51A877","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3a7f2299c98879ca8ccd34e0e77b20088b579473","datavalue":{"value":"Let \\(A\\) be a 0-1 matrix of dimension \\(n\\cdot m\\). Consider the following pair of linear programs  \\[  \\text{(L)}\\quad \\max x\\cdot 1,\\quad Ax\\leq 1,\\quad x\\geq 0;\\quad \\text{(D)}\\quad \\min y\\cdot 1,\\quad yA\\geq 1,\\quad y\\geq 0.  \\]  If integral solution constraints are added, they become dual pairs of packing and covering integer linear programs. Let \\(z\\) and \\(Z\\) be the integral optimum of (L) and (D), and q the common rational optimum of (L) and (D). The main results are that a tight inequality relating \\(z\\) and \\(q\\), and a best possible bound between \\(z\\) and \\(Z\\) can be found in the following form:  \\[  z\\geq \\frac{q^2}{n-(f-1)q^2/m}\\geq q^2/n,  \\]   \\[  Z\\leq \\begin{cases} \\min(n,3g) & \\text{if } m>e(nz)^{1/2}, \\\\ m & \\text{if }m<e(nz)^{1/2}, \\end{cases}  \\]  where \\(f\\) is the least column sum of \\(A\\), and \\(g(nz\\ln(m/(nz)^{1/2})^{1/2}\\). At end of the paper the autor suggest further interesting directions for research.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105488$18C501F4-36C8-4F1F-A571-0A5F07A27CA7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105488$E2DE8685-0824-4BF7-AA40-F287F423B69A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105488$BEEF975B-627D-4E38-831D-A17E8C5FDA82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105488$148DB4EF-A14A-4EA7-B7C1-8D4D2A16D287","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105488$8C86A2E4-648C-4186-8C26-ADEC47E17F68","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"231b220354dba69ef446a99d6ed35115ff0b0113","datavalue":{"value":"4059116","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105488$FCA0AB67-1E7B-422D-B008-BE54F15F6DF6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b143028f038d467eb3bd3557fd77e106757ce8f","datavalue":{"value":"pair of linear programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105488$0595FF57-754E-4EEA-A1E8-D7806CDB8054","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"093ef3cbea03ec661dc66ae3009ad13581b7249b","datavalue":{"value":"packing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105488$B876BE9A-45B5-44A4-A9C1-5E7440D26871","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dfccb6282b586deba8200ce91c0d4ea629113fe0","datavalue":{"value":"covering integer linear programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105488$D5E30E4F-9318-47A5-9874-BF76E2293711","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"7607038bef367a47d8dc064ae61f03313d5fd39c","datavalue":{"value":"Q105659276","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105488$E4F0A1E6-2F0C-4DEE-8D48-419AFB88069B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f8851f7d7ed4147f596ab1e98283df373347f7d6","datavalue":{"value":{"entity-type":"item","numeric-id":180312,"id":"Q180312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105488$B044310B-03D6-4FEF-9867-726CEDA3F730","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":"Q1105488$B7BDC666-F1CD-4D51-ABF5-5E8E4E642719","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5670f34f7f97e1f73ed327c2ad2e07b09b07d505","datavalue":{"value":{"entity-type":"item","numeric-id":1168988,"id":"Q1168988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105488$4B9B5C74-F180-4C8A-BF07-3A635ACC04ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a567a0bd5149009c58baa277d371437f0fed769","datavalue":{"value":{"entity-type":"item","numeric-id":1213733,"id":"Q1213733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105488$4C11B1F6-A944-43B5-9FEF-EC8A4F30DA83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7db3468346fcce29d2fe703e3816d1c0ffadbf3a","datavalue":{"value":{"entity-type":"item","numeric-id":1224109,"id":"Q1224109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105488$59636F07-6809-47FD-9DE5-87E6F66E5B38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5dcb4446087c3a1009df708ef3a2f3c1f3932cad","datavalue":{"value":{"entity-type":"item","numeric-id":5338788,"id":"Q5338788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105488$788E02B6-DD32-41EC-8283-5F12E0ADBBFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62d035f421ab9bd8eaa29b517b29669cf50cb87e","datavalue":{"value":{"entity-type":"item","numeric-id":1144028,"id":"Q1144028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105488$08A1433A-CC1C-4A28-9FCF-7C67557EF860","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"44c0136a0fce731f979b4c6db255bf8827cd8a0c","datavalue":{"value":"https://doi.org/10.1007/bf02122549","type":"string"},"datatype":"url"},"type":"statement","id":"Q1105488$CFEDFE0C-9DCA-483B-8ED5-D1C6AC378400","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b9509a02b60d942a85dc0ba56455e7378ec6b237","datavalue":{"value":"W2093321189","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105488$0DB61684-A6AF-4290-9088-C33993488F2E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c90ad877fd7e42469bf8dbd6a0662d47c7d879f","datavalue":{"value":{"entity-type":"item","numeric-id":3835750,"id":"Q3835750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"939b0e07772e3f62284470121aa8d2ef9cba8e20","datavalue":{"value":{"amount":"+0.8312109708786011","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":"Q1105488$51C7A689-B218-41AA-9D09-C411E6B28E63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"104dfc39e9ec41ce357ce7cab99436afd7755762","datavalue":{"value":{"entity-type":"item","numeric-id":4522859,"id":"Q4522859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"939b0e07772e3f62284470121aa8d2ef9cba8e20","datavalue":{"value":{"amount":"+0.8312109708786011","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":"Q1105488$4F0FEFE0-4046-4A53-8677-0431B92B2787","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7021e6b377c286ff4677475b66df0acdd8cb9df4","datavalue":{"value":{"entity-type":"item","numeric-id":1363966,"id":"Q1363966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36651467e6e3abb8d2918c7184661cccbde1df87","datavalue":{"value":{"amount":"+0.8117931485176086","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":"Q1105488$8198DE11-5854-4D4C-8714-89264427D58B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"346d26e576024c0ebd2645326fa66d026c8570de","datavalue":{"value":{"entity-type":"item","numeric-id":3352839,"id":"Q3352839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0d1bec49795ac2c90b5ba4a7a7129b2a537fd91","datavalue":{"value":{"amount":"+0.810869038105011","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":"Q1105488$B5DD662D-A6C1-422C-8A5D-4AD954E85F8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6601c703ddf0fd2ba4875f2b9041d5a848bcf20","datavalue":{"value":{"entity-type":"item","numeric-id":3694985,"id":"Q3694985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c78339fc8461b81785d7ed42d8afc5387e164de2","datavalue":{"value":{"amount":"+0.8097866177558899","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":"Q1105488$F7DE44D0-5A89-446D-BE25-C4762DA744EC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1105488","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1105488"}}}}}