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


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.


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


  Payday Loans In Missouri. Since its introduction in the market buying Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.