000164208 001__ 164208
000164208 005__ 20190316235045.0
000164208 0247_ $$2doi$$a10.1287/moor.1100.0470
000164208 022__ $$a1526-5471
000164208 02470 $$2ISI$$a000285340400005
000164208 037__ $$aARTICLE
000164208 245__ $$aDiameter of Polyhedra: Limits of Abstraction
000164208 269__ $$a2010
000164208 260__ $$c2010
000164208 336__ $$aJournal Articles
000164208 520__ $$aWe investigate the diameter of a natural abstraction of the 1-skeleton of polyhedra. Even if this abstraction is more general than other abstractions previously studied in the literature, known upper bounds on the diameter of polyhedra continue to hold here. On the other hand, we show that this abstraction has its limits by providing an almost quadratic lower bound.
000164208 6531_ $$aconvex geometry
000164208 6531_ $$adisjoint coverings
000164208 6531_ $$aHirsch conjecture
000164208 6531_ $$apolyhedra
000164208 6531_ $$aD-Step Conjecture
000164208 6531_ $$aSimplex Algorithm
000164208 6531_ $$aPolytopes
000164208 6531_ $$aGraphs
000164208 6531_ $$aCubes
000164208 700__ $$0240331$$g183121$$aEisenbrand, Friedrich
000164208 700__ $$0243824$$g188828$$aHähnle, Nicolai
000164208 700__ $$aRazborov, Alexander
000164208 700__ $$g183730$$aRothvoss, Thomas$$0243826
000164208 773__ $$j35$$tMathematics of Operations Research$$k4$$q786-794
000164208 8564_ $$uhttps://infoscience.epfl.ch/record/164208/files/limitsofabstraction-published.pdf$$zn/a$$s146496$$yn/a
000164208 909C0 $$xU11879$$0252111$$pDISOPT
000164208 909CO $$qGLOBAL_SET$$pSB$$ooai:infoscience.tind.io:164208$$particle
000164208 917Z8 $$x188828
000164208 937__ $$aEPFL-ARTICLE-164208
000164208 973__ $$rNON-REVIEWED$$sPUBLISHED$$aEPFL
000164208 980__ $$aARTICLE