Short simplex paths in lattice polytopes

We consider the problem of optimizing a linear function over a lattice polytope P contained in [0,k]^n and defined via m linear inequalities. We design a simplex algorithm that, given an initial vertex, reaches an optimal vertex by tracing a path along the edges of P of length at most O(n^6 k log k). The … Read more

On Dantzig figures from graded lexicographic orders

We construct two families of Dantzig figures, which are $d$-dimensional polytopes with $2d$ facets and an antipodal vertex pair, from convex hulls of initial subsets for the graded lexicographic (grlex) and graded reverse lexicographic (grevlex) orders on $\mathbb{Z}^{d}_{\geq 0}$. These polytopes have the same number of vertices $O(d^2)$ and the same number of edges $O(d^3)$, … Read more

Improvement of Kalai-Kleitman bound for the diameter of a polyhedron

Recently, Todd got 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 … Read more

An improved Kalai-Kleitman bound for the diameter of a polyhedron

Kalai and Kleitman established the bound $n^{\log(d) + 2}$ for the diameter of a $d$-dimensional polyhedron with $n$ facets. Here we improve the bound slightly to $(n-d)^{\log(d)}$. Citation School of Operations Research and Information Engineering, Cornell University, Ithaca NY, USA, February 2014 Article Download View An improved Kalai-Kleitman bound for the diameter of a polyhedron

A Proof by the Simplex Method for the Diameter of a (0,1)-Polytope

Naddef shows that the Hirsch conjecture is true for (0,1)-polytopes by proving that the diameter of any $(0,1)$-polytope in $d$-dimensional Euclidean space is at most $d$. In this short paper, we give a simple proof for the diameter. The proof is based on the number of solutions generated by the simplex method for a linear … Read more

The continuous d-step conjecture for polytopes

The curvature of a polytope, defined as the largest possible total curvature of the associated central path, can be regarded as the continuous analogue of its diameter. We prove the analogue of the result of Klee and Walkup. Namely, we show that if the order of the curvature is less than the dimension $d$ for … Read more

Polytopes and Arrangements : Diameter and Curvature

We introduce a continuous analogue of the Hirsch conjecture and a discrete analogue of the result of Dedieu, Malajovich and Shub. We prove a continuous analogue of the result of Holt and Klee, namely, we construct a family of polytopes which attain the conjectured order of the largest total curvature. Citation AdvOL-Report #2006/09 Advanced Optimization … Read more