TY - JOUR
T1 - A refinement of Todd's bound for the diameter of a polyhedron
AU - Sukegawa, Noriyoshi
AU - Kitahara, Tomonari
N1 - Funding Information:
The authors thank anonymous reviewers for constructive comments and suggestions. This research is supported in part by Grant-in-Aid for Science Research (A) 26242027 of Japan Society for the Promotion of Science (JSPS) , Grant-in-Aid for Science Research (B) 24310112 of JSPS , and Grant-in-Aid for JSPS Fellows.
Publisher Copyright:
© 2015 Published by Elsevier B.V.
PY - 2015
Y1 - 2015
N2 - Recently, Todd obtained a new bound on the diameter of a polyhedron using an analysis due to Kalai and Kleitman in 1992. In this short note, we prove that the bound by Todd can further be improved. Although our bound is not valid when the dimension is 1 or 2, it is tight when the dimension is 3, and fits better for a high-dimensional polyhedron with a large number of facets.
AB - Recently, Todd obtained a new bound on the diameter of a polyhedron using an analysis due to Kalai and Kleitman in 1992. In this short note, we prove that the bound by Todd can further be improved. Although our bound is not valid when the dimension is 1 or 2, it is tight when the dimension is 3, and fits better for a high-dimensional polyhedron with a large number of facets.
UR - http://www.scopus.com/inward/record.url?scp=84983179914&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84983179914&partnerID=8YFLogxK
U2 - 10.1016/j.orl.2015.07.001
DO - 10.1016/j.orl.2015.07.001
M3 - Article
AN - SCOPUS:84983179914
SN - 0167-6377
VL - 43
SP - 534
EP - 536
JO - Operations Research Letters
JF - Operations Research Letters
IS - 5
ER -