## 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

**Abstract:**

We study the combinatorial diameter of partition polytopes, a special class of transportation polytopes. They are associated to partitions of a set *X={x*_{1}, … ,x_{n}} of items into clusters *C*_{1}, … ,C_{k} 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**

**Abstract:**

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**

**Abstract:**

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.