On the diameter of partition polytopes and vertex-disjoint cycle cover (Q378108): Difference between revisions

The author gives three bounds on the combinatorial diameter of partition polytopes, a special class of transportation polytopes. They are associated to partitions of a set \(X=\left\{ x_{1}.\dots ,x_{n}\right\} \) of items into \(k\) clusters \(C_{1},\dots ,C_{k}\) of prescribed sizes \(k_{1}\geq \dots \geq k_{k}.\) \noindent The author derives upper bounds on the diameter in the form of \( k_{1}+k_{2},n-k_{1}\,\;\)and \(\left[ \frac{n}{2}\right] .\) Also, he gives exact diameters for partition polytopes with \(k=2\) or \(k=3\) and prove that, for all \(k\geq 4\) and all \(k_{1},k_{2}\), there are cluster sizes \( k_{3},\dots ,k_{k}\) such that the diameter of the corresponding partition polytope is at least \(\left[ \frac{4}{3}k_{2}\right] \). Finally, the author provides an \(O\left( n\left( k_{1}+k_{2}\left( \sqrt{k}-1\right) \right) \right) \) algorithm for an edge-walk connecting two given vertices of a partition polytope.