English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This dissertation investigates the geometric combinatorics of convexpolytopes and connections to the behavior of the simplex method for linearprogramming. We focus our attention on transportation polytopes, which are setsof all tables of non-negative real numbers satisfying certain summationconditions. Transportation problems are, in many ways, the simplest kind oflinear programs and thus have a rich combinatorial structure. First, we givenew results on the diameters of certain classes of transportation polytopes andtheir relation to the Hirsch Conjecture, which asserts that the diameter ofevery $d$-dimensional convex polytope with $n$ facets is bounded above by$n-d$. In particular, we prove a new quadratic upper bound on the diameter of$3$-way axial transportation polytopes defined by $1$-marginals. We also showthat the Hirsch Conjecture holds for $p \times 2$ classical transportationpolytopes, but that there are infinitely-many Hirsch-sharp classicaltransportation polytopes. Second, we present new results on subpolytopes oftransportation polytopes. We investigate, for example, a non-regulartriangulation of a subpolytope of the fourth Birkhoff polytope $B_4$. Thisimplies the existence of non-regular triangulations of all Birkhoff polytopes$B_n$ for $n \geq 4$. We also study certain classes of network flow polytopesand prove new linear upper bounds for their diameters.

Geometric Combinatorics of Transportation Polytopes and the Behavior of the Simplex Method