We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
On the diameter of partition polytopes and vertex-disjoint cycle cover.
- Authors
Borgwardt, Steffen
- Abstract
We study the combinatorial diameter of partition polytopes, a special class of transportation polytopes. They are associated to partitions of a set X = { x1, . . . , xn} of items into clusters C1, . . . , Ck of prescribed sizes κ1 ≥ · · · ≥ κk. We derive upper bounds on the diameter in the form of κ1 + κ2, n − κ1 and $${\lfloor \frac{n}{2} \rfloor}$$ . This is a direct generalization of the diameter-2 result for the Birkhoff polytope. The bounds are established using a constructive, graph-theoretical approach where we show that special sets of vertices in graphs that decompose into cycles can be covered by a set of vertex-disjoint cycles. Further, we give exact diameters for partition polytopes with k = 2 or k = 3 and prove that, for all k ≥ 4 and all κ1, κ2, there are cluster sizes κ3, . . . , κk such that the diameter of the corresponding partition polytope is at least $${\lceil \frac{4}{3} \kappa_2 \rceil}$$ . Finally, we provide an $${O(n(\kappa_1 + \kappa_2(\sqrt{k} - 1)))}$$ algorithm for an edge-walk connecting two given vertices of a partition polytope that also adheres to our diameter bounds.
- Subjects
POLYTOPES; CONVEX polytopes; TOPOLOGY; BIRKHOFF'S theorem (Relativity); RELATIVISTIC theorems (Relativity)
- Publication
Mathematical Programming, 2013, Vol 141, Issue 1/2, p1
- ISSN
0025-5610
- Publication type
Article
- DOI
10.1007/s10107-011-0504-9