Tail diameter upper bounds for polytopes and polyhedra

Autor:	Gallagher, J. Mackenzie, Kim, Edward D.
Rok vydání:	2016
Předmět:	Mathematics - Combinatorics Mathematics - Optimization and Control 05C12 90C05
Druh dokumentu:	Working Paper
Popis:	In 1992, Kalai and Kleitman proved a quasipolynomial upper bound on the diameters of convex polyhedra. Todd and Sukegawa-Kitahara proved tail-quasipolynomial bounds on the diameters of polyhedra. These tail bounds apply when the number of facets is greater than a certain function of the dimension. We prove tail-quasipolynomial bounds on the diameters of polytopes and normal simplicial complexes. We also prove tail-polynomial upper bounds on the diameters of polyhedra. Comment: 15 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1603.04052 Zobrazit plný text záznamu View this record from Arxiv