Invited Session Mon.3.H 3013

Monday, 15:15 - 16:45 h, Room: H 3013

Cluster 2: Combinatorial optimization [...]

Constrained clustering


Chair: Peter Gritzmann



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

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


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.



Monday, 15:45 - 16:10 h, Room: H 3013, Talk 2

Anastasia Shakhshshneyder
Hardness and non-approximability of constrained clustering

Coauthors: Andreas Brieden, Peter Gritzmann


This talk is devoted to constrained clustering, where one would like to divide a given set of objects into groups according to some objective function. The objects are usually represented as points in the Minkowski space, and the objective function is a function of the distances between them. We assume that the points have weights and the total weight of points in a cluster is prescribed to be in a given interval.
The constrained clustering problems are known to be NP-hard. But there is not much knowledge about their approximation status. In this talk we present new inapproximability results. In particular, we show that if the dimension is a part of the input, the problems are APX-hard and do not admit a 1.09-approximation. These results hold even if the points have equal weights and an overlapping of the clusters is allowed. Moreover, when fractional assignments of the points are not permitted, there is no polynomial-time 2|x|-approximate algorithm, where |x| is the size of an input x. The hardness persists even if the points lie on a line.



Monday, 16:15 - 16:40 h, Room: H 3013, Talk 3

Andreas Brieden
Constrained clustering with convex objective function

Coauthor: Peter Gritzmann


In this talk the computation of strongly and weakly balanced clusterings that are optimal with respect to the sum of pairwise cluster distances is considered. As it turns out,
the problem can be reduced to a well studied norm-maximization problem over much lower dimensional polytopes called gravity polytopes. The vertices of these polytopes are closely related to power diagrams which implies nice properties of any optimal clustering and also of approximate solutions. Furthermore this reduction allows for much better approximation results.


  Payday Loans Florida can help you in trying times, but be sure to know the laws necessary for your loan application. If you have already decided to take Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.