{"entities":{"Q1196197":{"pageid":1206946,"ns":120,"title":"Item:Q1196197","lastrevid":42937301,"modified":"2025-07-16T05:02:59Z","type":"item","id":"Q1196197","labels":{"en":{"language":"en","value":"Upper bounds for the diameter and height of graphs of convex polyhedra"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 77883"}},"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":"Q1196197$11C921C5-6C7B-4D85-946A-1A9F307324B4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d5ada3aa593241a9de7c914025acd1c3dbdb3ee9","datavalue":{"value":{"text":"Upper bounds for the diameter and height of graphs of convex polyhedra","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1196197$3F4A6458-F560-4AF1-B539-2E77C4A8AC1F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"84583e3be275458e507201eeea7c17cd0e16ae84","datavalue":{"value":"0764.52003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196197$75972A56-C86D-4187-A1C9-9245D082586F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4a699b86f223dc18091a1d40fd3a93dd2ee493cc","datavalue":{"value":"10.1007/BF02293053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196197$6B37396C-643B-42B4-8832-4D8C26C8474B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f85f18c63cbc91d82706e47b2a3a665a27a11982","datavalue":{"value":{"entity-type":"item","numeric-id":177917,"id":"Q177917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196197$9E9DE786-91C2-49A5-B7BF-86BB37A74DAB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b6f367138a9ac2b85113cfed5a6fd5bedcc8944c","datavalue":{"value":{"entity-type":"item","numeric-id":178842,"id":"Q178842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196197$657B4B70-E90E-4E26-9FE6-0F421FE68119","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8042fe0599241970cf427c9ca68a1764be1ca806","datavalue":{"value":{"time":"+1992-12-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1196197$466707D4-700B-4383-A1AD-AB65A97ED24D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c644fedd7361b8410355ad85bd60f5f476390658","datavalue":{"value":"https://eudml.org/doc/131225","type":"string"},"datatype":"url"},"type":"statement","id":"Q1196197$0C1F3D97-4E64-443E-A9BC-D7FDE3D80430","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cae3db7b6a34232baf10cd02b7173aa603540ce3","datavalue":{"value":"A well-known conjecture of Hirsch related to the complexity of the simplex algorithm for linear programming is that the diameter of the edge-graph of a convex polyhedron is bounded above by a linear function of its dimension \\(d\\) and number of facets \\(n\\). However, no bound is known which is even polynomial in \\(d\\). In fact, this paper exhibits the first quasipolynomial upper bound for the diameter as \\(n^{2\\log d+3}\\).   It is also shown that the height, i.e. maximal length of a shortest path along which an objective function is nondecreasing, is logarithmically bounded above by \\(2(\\sqrt n)\\log n\\). Although this result does not necessarily lead to a simplex pivoting rule with subexponential behaviour, the author announces such an, as yet unpublished, algorithm.   Finally it is shown that both the diameter and the height of any \\(d\\)- polytope, in which any \\(k\\)-face has at most \\(rk\\) facets with \\(r\\) at least 2, are polynomial in \\(d\\). Examples of such polyhedra are the feasible sets of generalized flow problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196197$DFEB09C1-5D41-42E8-9D09-35B965AF770B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"78931806833c54190437f3675cf624ba3d256107","datavalue":{"value":"52B05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196197$C13E69FA-296C-4ED7-9BA0-F4FBC13A8B4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8ede024a2e42be41193baf32f90dd58f10db2ea3","datavalue":{"value":"52B12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196197$D91C60AE-0EF5-44F4-A99B-2384F7924A26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196197$DDE9635C-24B0-4F1B-BCED-9672C80E5B71","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cd79668a339913f030939b119f87e8e6a44455b3","datavalue":{"value":"77883","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196197$9E8686A0-508B-41E0-B0E4-E90ED0AEAEBB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"335140c456bd2d47737ef511c95990b99cf88773","datavalue":{"value":"Hirsch conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196197$E065C691-9CD5-487D-A6FB-D026934FA969","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6dc4e15c0d0868d3f0f78209d751ac4d4e61e8fe","datavalue":{"value":"quasi-polynomial bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196197$1CC11034-1F94-4649-9BF4-0139FD7171D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd227adb1378edbe90691dff18511cebed6b0036","datavalue":{"value":"diameter","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196197$51AD380D-BB52-487A-A305-E52521BC2402","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"0bc8ca98cd6eec00f8505a8067353c2364df9a22","datavalue":{"value":"Q56503922","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196197$29C25065-71A0-4F90-B544-A57A33B97E90","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5e09f3da1a7483864918926ab5885138a8f45aaa","datavalue":{"value":{"entity-type":"item","numeric-id":166210,"id":"Q166210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196197$5C58840C-C2FE-4036-80F4-D643C224938B","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":"Q1196197$DF317ACB-83F7-433D-9200-5A6DB45CD080","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c3177d65ab8092e706f97dbca84caa19fb8627f","datavalue":{"value":{"entity-type":"item","numeric-id":5567009,"id":"Q5567009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196197$2B434FF5-A9E2-43E5-8626-6F03990534D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a43ca27cba6b8cbde68d00987a946f9cde333444","datavalue":{"value":{"entity-type":"item","numeric-id":3844775,"id":"Q3844775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196197$044481A3-E0F9-431A-81F7-9B7870273A56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f9f7fa55796e4289729d35a451bba230d60cf4e","datavalue":{"value":{"entity-type":"item","numeric-id":3352816,"id":"Q3352816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196197$395DD932-CD88-4886-B0D5-75DD6EBB8E0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff8fea9a5dba7c0c825c98a79aa7f9c13491987b","datavalue":{"value":{"entity-type":"item","numeric-id":5547252,"id":"Q5547252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196197$B286EA24-36C6-4DEE-BE3C-1BD55D5C4895","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78f791484e404eb6a7533155ea06b53c04f16719","datavalue":{"value":{"entity-type":"item","numeric-id":3974981,"id":"Q3974981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196197$1146DB30-B94E-4004-A8E3-F6CBD63B16BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c83d3ac1eb6f199086933e273cb1928bcf98889","datavalue":{"value":{"entity-type":"item","numeric-id":4005821,"id":"Q4005821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196197$E9A35AF2-10EB-45CE-AB42-028CBAA45C6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"747b1202e75ae6c845857969c20ad98a79e741b2","datavalue":{"value":{"entity-type":"item","numeric-id":3769521,"id":"Q3769521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196197$7D539F2E-4E09-43E4-85DA-201F85AAC522","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88c255f2e6ecd34a611f1ccf928bf197acbeea63","datavalue":{"value":{"entity-type":"item","numeric-id":4051879,"id":"Q4051879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196197$A0FB9E99-9B6A-400D-9BB0-8F9BA53EECFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c47e2e874f495f74e72b8cb1bf38db27697eaef6","datavalue":{"value":{"entity-type":"item","numeric-id":2529023,"id":"Q2529023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196197$4D7B4785-6DC5-4C0A-817D-8BF00079C1E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a733cebb411897bab640034bf1b5839f3d71cd1","datavalue":{"value":{"entity-type":"item","numeric-id":5598187,"id":"Q5598187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196197$1869F851-97A5-4350-90DC-12E6ACB97F2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2a3c39007748791bafb333f69ae495293a77f79","datavalue":{"value":{"entity-type":"item","numeric-id":5621734,"id":"Q5621734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196197$FDE27DB6-EC21-4F27-B327-1E7C9E25EDC4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"efbb81f7b0ec269a1f6c6533909bb478038c113c","datavalue":{"value":{"entity-type":"item","numeric-id":4005821,"id":"Q4005821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3459598170f176a0419bb035a4f289596bb81f46","datavalue":{"value":{"amount":"+0.9201637","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1196197$23DB6A0C-8C0C-4B93-BCE2-B1472829B3DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"991a0fd855203837a05e338d5a80cc009197b6c7","datavalue":{"value":{"entity-type":"item","numeric-id":3974981,"id":"Q3974981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41c03e483ff4b192c2144e05effb2360a2b03a6e","datavalue":{"value":{"amount":"+0.9092501","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1196197$1D52226A-6B3B-48AC-8281-5FDC50C09A2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac4cff9562b4cef3812c82f0995aeb05012cd234","datavalue":{"value":{"entity-type":"item","numeric-id":4915386,"id":"Q4915386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"150bcfb8a45df8608b2d0852c097799ac4c4c89b","datavalue":{"value":{"amount":"+0.90850663","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1196197$8B81DE1D-3AA9-4E33-95B9-42FDA3A928ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f23783508312f0e839f3107667fe05236254c4e","datavalue":{"value":{"entity-type":"item","numeric-id":4699167,"id":"Q4699167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86027445cecbdd606c6ca7e89068e7a820d490fb","datavalue":{"value":{"amount":"+0.9083974","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1196197$260DC102-08A0-4D0A-8ACF-6493283BF801","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ade9a2f81c5a83cbbcfc1a0eaed6b28da30cb25","datavalue":{"value":{"entity-type":"item","numeric-id":2324633,"id":"Q2324633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1aba2623e2ebd8ebc3baec2fdf8afae1e59d27d3","datavalue":{"value":{"amount":"+0.9062711","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1196197$1919684A-6A1F-4AFD-9B50-81FAF873C767","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9bfc5c039e50575abeaeb1992ce0164d853e0264","datavalue":{"value":{"entity-type":"item","numeric-id":4894616,"id":"Q4894616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f095607a1b0ade8ac3b477b502957aa27c985f56","datavalue":{"value":{"amount":"+0.90203667","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1196197$6B8DC91C-4FDF-45DB-943E-FCA45454299E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a0919bcd1d069a37ac17662b3027fc75003421f","datavalue":{"value":{"entity-type":"item","numeric-id":5299904,"id":"Q5299904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa04ac25ca2592f6611f8595d44be0804511fc8b","datavalue":{"value":{"amount":"+0.9019506","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1196197$34B89DE3-697B-44EA-88D9-B6FBF5DDE287","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf17d4eb076272ceb97cf00f636996c75a288637","datavalue":{"value":{"entity-type":"item","numeric-id":3033789,"id":"Q3033789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4d95e2514ca7949209ee8361bc9910d3371a81c","datavalue":{"value":{"amount":"+0.89551604","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1196197$DDE0242B-B961-4F21-9BA0-50A4E53CBA66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e58c6980fdd291515ae60d70e9c2995d5da5187","datavalue":{"value":{"entity-type":"item","numeric-id":2459503,"id":"Q2459503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5a164db34822d9bc9c97f33085dbaf512e8eaed","datavalue":{"value":{"amount":"+0.8929088","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1196197$C749F7C5-BE7D-4C03-A36C-CAAC22B34470","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"388f66a02ea9b38cfef566c6d4073e6381ad3b52","datavalue":{"value":{"entity-type":"item","numeric-id":4455475,"id":"Q4455475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a50d04feb701ce937a2ce2ae37866453a1d3f7ee","datavalue":{"value":{"amount":"+0.89164424","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1196197$B3C6B6C8-CC7A-4C1F-A45B-DF553F91A335","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1196197","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1196197"}}}}}