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

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

Talk 2 of the invited session Mon.3.H 3013

**"Constrained clustering"** [...]

Cluster 2

**"Combinatorial optimization"** [...]