{"entities":{"Q1198616":{"pageid":1209365,"ns":120,"title":"Item:Q1198616","lastrevid":66852528,"modified":"2026-04-12T13:17:51Z","type":"item","id":"Q1198616","labels":{"en":{"language":"en","value":"On the convex hull of feasible solutions to certain combinatorial problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 90146"}},"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":"Q1198616$A8B99CFF-C860-464D-94CC-E0A162B5762E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"da345da20cdb3c48c14fe9460664b212c732f876","datavalue":{"value":{"text":"On the convex hull of feasible solutions to certain combinatorial problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1198616$4BC0FC62-0D4F-4FA1-B54E-EF43D679F9DE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a0ff37c8bcbdde00cc5f8cac9105f901c10b94f4","datavalue":{"value":"0764.90070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198616$AD2C5F96-1D50-48BA-881F-E3DA2C5282F8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6d3d51107f727e8c5619d966f7d79edcd912a0f7","datavalue":{"value":"10.1016/0167-6377(92)90055-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198616$5F62EF47-AB5E-4A1F-8852-DCFC40DDE1C2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"37955629647df45e738d39554e9a542b3b76129d","datavalue":{"value":{"entity-type":"item","numeric-id":423918,"id":"Q423918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198616$EF4A86B6-70D7-4B2A-BCB7-7CB887A0E76C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"26ab423245825b358864252a7442720e0042a25c","datavalue":{"value":{"entity-type":"item","numeric-id":1198615,"id":"Q1198615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198616$1BAFAFBB-9C48-41D2-B994-F58BFE66B0D6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198616$E0C6A3BA-3687-4010-9B4A-FCCB371D7B80","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1198616$78264822-8E98-43E3-B448-A5AB58E402B0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cbc7763a4ea79fcef5575b5baf8eb92a7c9a04d6","datavalue":{"value":"This paper deals with the question: In which cases is the convex hull of a finite union of (unbounded) convex polyhedra closed and hence a convex polyhedron itself? First the authors present three examples of combinatorial problems (the Steiner graphical Travelling Salesman problem, a nonpreemptive single-machine scheduling problem with changeover times and a preemptive single-machine scheduling problem), where the convex hull of the feasible set is not closed, and therefore not a polyhedron.   The most essential result: Assume that the convex hull of the union \\(C\\) of a finite collection \\(C_ i\\), \\(i\\in I\\), of convex polyhedra contains no line. Then the convex hull of \\(C\\) is a convex polyhedron if and only if for all extreme rays \\(\\{x\\}+\\text{cone}\\{d\\}\\) of \\(\\text{cl conv } C\\), and for all scalars \\(\\mu\\geq 0\\), there exists \\(\\mu'\\geq \\mu\\) such that \\(x+\\mu'd\\in C\\) (the corresponding formulation in the paper contains a mistake). This theorem is applied to certain combinatorial problems (Steiner graphical Travelling Salesman problems, Steiner Chinese Postman problems, nonpreemptive scheduling problems with changeover times, preemptive scheduling problems).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198616$DE95FE3D-5430-4A75-BA6B-660FE9668569","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198616$CA06B90D-AE12-4F5A-BA29-DD8786ED2074","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198616$A84FDB05-4074-4206-BD8B-F02DB3D8DC22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8ede024a2e42be41193baf32f90dd58f10db2ea3","datavalue":{"value":"52B12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198616$F1B20439-5AC8-4803-AE68-DF9E53F6F148","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198616$04A5CD7A-1B6B-4345-BD31-0902E822AA39","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"332b103890b89dbde801be7274a29d0c806f887c","datavalue":{"value":"90146","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198616$962F0548-F04D-4CE5-B812-E54794CEB31C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"697626a6c5ea4a7921eba4e0f3fdba17e2e290d9","datavalue":{"value":"convex hull","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198616$1D063A74-CCCF-4846-80AF-84BFF44DF10A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c6832e30adf36ba5cce0db72911b3c0dda821c66","datavalue":{"value":"finite union","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198616$A5CBC9B4-B24A-44E3-A0AB-5FBDF52BD257","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e8350709a8e8e9c85e07cae37ea0e93d9da7fdf1","datavalue":{"value":"convex polyhedron","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198616$33D4DEF3-87B4-4937-B0A6-5028A229AF68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"58a7b774337ec9b99821a727fc110f3ddbd8ca03","datavalue":{"value":"nonpreemptive single- machine scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198616$3EFBA892-17CE-47D0-A6EC-71975821C137","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f6ea406ef36e1810d468b672efc85eebb5f97473","datavalue":{"value":{"entity-type":"item","numeric-id":566922,"id":"Q566922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198616$2F33AC29-E1BF-45D6-B354-4258208881DD","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":"Q1198616$58C5BFD7-C1FE-4D7E-AD67-D393D2673B13","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8a3c8cec9388de3db111fd75fbc7853f333e91b5","datavalue":{"value":"https://doi.org/10.1016/0167-6377(92)90055-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1198616$C1705C3E-0AA5-40BF-9B3F-5DCFEF0CA494","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9cbdd79e9eab05f6983ecb4ebe88f7a638567449","datavalue":{"value":"W2020059491","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198616$274D3545-2BB3-4542-A95A-6A1F10C6F772","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c921ee3c16e3b8c56efe589ca197ea2e4a0f3af","datavalue":{"value":{"entity-type":"item","numeric-id":3705207,"id":"Q3705207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198616$35F2BE8E-D732-447F-B144-4FE726562FFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"477472125047662488d35f63e8eeef0d620af231","datavalue":{"value":{"entity-type":"item","numeric-id":1115345,"id":"Q1115345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198616$92650323-F00A-4D9B-A67A-968E7656A13C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9e8a2a2ba09a34750ac91787a928d451826bfdc","datavalue":{"value":{"entity-type":"item","numeric-id":3675933,"id":"Q3675933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198616$83645004-48EC-49F8-90BD-10CCFEB0CD43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8877a49dfa06c845f3b0cbac2a5aa8e1d29e04f0","datavalue":{"value":{"entity-type":"item","numeric-id":4171871,"id":"Q4171871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198616$38107777-F2DA-4E75-B8C7-52E686DBA830","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":"Q1198616$9021EFF8-870E-4B76-8664-A30B5E418342","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fac46e183e471ef792ae3f5374a5fad8885e2956","datavalue":{"value":{"entity-type":"item","numeric-id":1803611,"id":"Q1803611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198616$1EED79B9-B3F9-4497-B9DF-5C10D3F642FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2fee5e5fa5b3294832d2fbed1f8cbbf46559b91b","datavalue":{"value":{"entity-type":"item","numeric-id":3971735,"id":"Q3971735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198616$E2B32392-545D-4C31-AA64-9C9E4BFF0B13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2aa4eeac790205c4037ea67c80426826ddde338","datavalue":{"value":{"entity-type":"item","numeric-id":5638112,"id":"Q5638112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198616$762020EA-DBFE-45D4-AFBB-1C00867970A4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae827a0583aade64978e88c63a271473d11ea76b","datavalue":{"value":{"entity-type":"item","numeric-id":1115345,"id":"Q1115345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a519faf139d2d362e65b26e197b0ae25ac49671","datavalue":{"value":{"amount":"+0.7839836478233337","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":"Q1198616$063C56D0-9C67-4B40-8E5B-232B937E1393","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"341155efca36ba78672ba125a4a14595a3b35d85","datavalue":{"value":{"entity-type":"item","numeric-id":1104856,"id":"Q1104856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"804a1524e04c92fb8514f0601b5ae9aadf1f5f5c","datavalue":{"value":{"amount":"+0.7640597820281982","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":"Q1198616$FB7AD053-B963-4ACB-97E7-E0D91D8C8F5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"efb9410108de9de8917c49d5b7b4030730c78354","datavalue":{"value":{"entity-type":"item","numeric-id":5752291,"id":"Q5752291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9bb7821dc76a24e3621dbd6cd8112bc6efcfedb9","datavalue":{"value":{"amount":"+0.7567152976989746","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":"Q1198616$DE709712-0D9A-48E2-80FE-A060779F4F89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d926dddaaf5ffb40cfa001fe05484f11c4d53df","datavalue":{"value":{"entity-type":"item","numeric-id":3813613,"id":"Q3813613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f58352a2c7899771aaaee1d9772dc06c3d11f1c","datavalue":{"value":{"amount":"+0.7503408193588257","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":"Q1198616$3DAF7254-83B7-482D-8974-6C2B2CD64EB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f142615c318b94adb1456e14615375ee9950a3c","datavalue":{"value":{"entity-type":"item","numeric-id":1894936,"id":"Q1894936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"790526b9b4774192b8590a91c01a6f25be73183b","datavalue":{"value":{"amount":"+0.7427413463592529","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":"Q1198616$84F7AEF3-6807-4125-94AC-D4DEC5E99887","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the convex hull of feasible solutions to certain combinatorial problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_convex_hull_of_feasible_solutions_to_certain_combinatorial_problems"}}}}}