◍wovepaper
SearchResearchersInstitutions
Sign in
math.OCApr 1, 2016
13
citations (OpenAlex)
authors
  • Noriyoshi Sukegawa
institutions
  • Chuo University
arXiv abstractPDF
paper

Improving bounds on the diameter of a polyhedron in high dimensions

arXiv:1604.04039 · doi:10.1016/j.disc.2017.04.005

Abstract

In 1992, Kalai and Kleitman proved that the diameter of a d-dimensional polyhedron with n facets is at most n2+log2​d. In 2014, Todd improved the Kalai-Kleitman bound to (n−d)log2​d. We improve the Todd bound to (n−d)−1+log2​d for n≥d≥7, (n−d)−2+log2​d for n≥d≥37, and (n−d)−3+log2​d+O(1/d) for n≥d≥1.

References in corpus (11)

  • Lectures on 0/1-polytopes
  • A counterexample to the Hirsch conjecture
  • The width of 5-dimensional prismatoids
  • Recent progress on the combinatorial diameter of polytopes and simplicial complexes
  • Improved bounds on the diameter of lattice polytopes
  • Polyhedral graph abstractions and an approach to the Linear Hirsch Conjecture
  • Hirsch polytopes with exponentially long combinatorial segments
  • On the diameter of lattice polytopes
  • Tail diameter upper bounds for polytopes and polyhedra
  • An improved upper bound on the diameters of subset partition graphs
  • A simple proof of tail--polynomial bounds on the diameter of polyhedra

Cited by in corpus (4)

  • Improved bounds on the diameter of lattice polytopes
  • A double-pivot simplex algorithm and its upper bounds of the iteration numbers
  • A simple proof of tail--polynomial bounds on the diameter of polyhedra
  • A note on the diameter of convex polytope
◍wovepaper

Papers, researchers and institutions, woven together.

Explore
  • Search
  • Researchers
  • Institutions
Account
  • Library
  • Chat
Data
  • arXiv.org
  • Semantic Scholar
  • OpenAlex
  • Latest RSS
AboutContactPrivacyDevelopersllms.txtopenapi.json
Not affiliated with arXiv. Researcher data from Semantic Scholar (ODC-BY) and OpenAlex.