Transportation Problems and Simplicial Polytopes That Are Not Weakly Vertex‐Decomposable

Transportation Problems and Simplicial Polytopes That Are Not Weakly Vertex‐Decomposable

0.00 Avg rating0 Votes
Article ID: iaor20127200
Volume: 37
Issue: 4
Start Page Number: 670
End Page Number: 674
Publication Date: Nov 2012
Journal: Mathematics of Operations Research
Authors: ,
Keywords: optimization
Abstract:

Provan and Billera defined the notion of weak k‐decomposability for pure simplicial complexes in the hopes of bounding the diameter of convex polytopes. They showed the diameter of a weakly k‐decomposable simplicial complex Δ is bounded above by a polynomial function of the number of k‐faces in Δ and its dimension. For weakly 0‐decomposable complexes, this bound is linear in the number of vertices and the dimension. In this paper we exhibit the first examples of non‐weakly 0‐decomposable simplicial polytopes. Our examples are in fact polar to certain transportation polytopes.

Reviews

Required fields are marked *. Your email address will not be published.