×

On the diameter of partition polytopes and vertex-disjoint cycle cover. (English) Zbl 1288.90049

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}.\) 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.

MSC:

90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Klee, V.; Witzgall, C.; Dantzig, G. B. (ed.); Veinott, A. F. (ed.), Facets and vertices of transportation polytopes, 257-282 (1968), Richmond
[2] Kovalev M., Yemelichev V., Kratsov M.: Polytopes, Graphs and Optimization. Cambridge University Press, Cambridge (1984)
[3] De Loera, J. A.: Transportation polytopes: a twenty year update. University of California, Davis. Slides of Talk at Workshop on Convex Sets and their Applications. Banff (2006)
[4] De Loera J.A., Kim E.D., Onn S., Santos F.: Graphs of transportation polytopes. J. Comb. Theory Ser. A. 116(8), 1306-1325 (2009) · Zbl 1229.05190 · doi:10.1016/j.jcta.2009.03.010
[5] Borgwardt, S.: A Combinatorial optimization approach to constrained clustering. Ph.D. Thesis. TU München (2010)
[6] Basu S., Davidson I., Wagstaff K.: Clustering with Constraints: Advances in Algorithms, Theory and Applications. Chapman & Hall, London (2008)
[7] Brightwell, G., Heuvel, J., Stougie, L.: A linear bound on the diameter of the transportation polytope. SPOR rep. 2003-12. Technical University Eindhoven (2003) · Zbl 1017.05058
[8] Naddef D.: The Hirsch conjecture is true for (0,1)-polytopes. Math. Program. 45(1), 109-110 (1989) · Zbl 0684.90071 · doi:10.1007/BF01589099
[9] Matsui T., Tamura S.: Adjacency on Combinatorial Polyhedra. Discret. Appl. Math. 56, 311-321 (1993) · Zbl 0818.90070 · doi:10.1016/0166-218X(94)00092-R
[10] Balinski M., Russakoff A.: On the assignment polytope. SIAM Rev. 16, 4 (1974) · Zbl 0269.90051 · doi:10.1137/1016083
[11] Diestel R.: Graph Theory. Graduate Texts in Mathematics, vol. 173. Springer, Berlin (2006) · Zbl 1086.05001
[12] Guralnick R., Perkinson D.: Permutation polytopes and indecomposable elements in permutation groups. J. Comb. Theory Ser. A. 113, 1243-1256 (2006) Elsevier Science · Zbl 1108.52014 · doi:10.1016/j.jcta.2005.11.004
[13] Zhang, C.Q.: Integer Flows and Cycle Cover of Graphs. CRC Press (1997)
[14] Ishigami Y., Jiang T.: Vertex-disjoint cycles containing prescribed vertices. J. Graph Theory. 42(4), 276-296 (2003) · Zbl 1017.05058 · doi:10.1002/jgt.10090
[15] Dinic E.A.: Algorithm for solution of a problem of maximum flow in a network with power estimation. Sov. Math. Dokl. 11(5), 1277-1280 (1970) · Zbl 0219.90046
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.