Monday, 15:15 - 15:40 h, Room: H 3013

 

Steffen Borgwardt
On the diameter of partition polytopes and vertex-disjoint cycle cover

 

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 ⌊ n⁄2 ⌋ . This is a direct generalization of the diameter-2 result for the Birkhoff polytope. The bounds are established by a constructive, graph-theoretical approach which reveals that special sets of vertices in graphs that decompose into cycles can be covered by a set of vertex-disjoint cycles. Finally, 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 ⌈ 4⁄3 κ 2.

 

Talk 1 of the invited session Mon.3.H 3013
"Constrained clustering" [...]
Cluster 2
"Combinatorial optimization" [...]

 

  Payday Loans In Ohio. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cheap Cialis was obtained in Europe, Australia, New Zealand.